{x}
blog image

Shortest Way to Form String

Solution Explanation: Shortest Way to Form String

This problem asks for the minimum number of subsequences of the source string needed to form the target string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The most efficient approach is a greedy algorithm using two pointers. We iterate through the target string, trying to find the longest possible subsequence within the source string at each step.

Algorithm:

  1. Initialization: We initialize a counter ans to 0 (representing the number of subsequences) and a pointer j to 0 (pointing to the current character in the target string).

  2. Iteration: We iterate while j is less than the length of target. Inside the loop:

    • We use a nested loop (or a helper function as shown in the code examples) to find the longest subsequence of source that matches a prefix of the remaining target string (starting from index j). This inner loop advances the pointer j in target whenever a match is found.
    • If the inner loop completes without finding any matches for the current j position in target, it means the target string cannot be formed using subsequences from the source string; we return -1.
    • If a subsequence is found (inner loop advances j), we increment ans (one more subsequence needed) and continue to the next portion of the target string.

Time Complexity: O(m*n), where 'm' is the length of source and 'n' is the length of target. The nested loops (or repeated calls to the helper function) lead to this complexity in the worst case.

Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Examples (with detailed comments):

Python:

class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        m, n = len(source), len(target)  # lengths of source and target strings
        ans = 0  # counter for subsequences
        j = 0  # pointer for target string
 
        while j < n:  # Iterate until all characters in target are processed
            i = 0  # pointer for source string
            k = j # keep track of original j to check if any progress was made
            while i < m and j < n:
                if source[i] == target[j]:
                    j += 1  # move target pointer if match found
                i += 1  #always move source pointer
 
            if k == j: #check if j was moved at all during inner loop
                return -1  # Impossible to form target using source subsequences
            ans += 1  # Increment subsequence count
 
        return ans

Java:

class Solution {
    public int shortestWay(String source, String target) {
        int m = source.length(), n = target.length();
        int ans = 0, j = 0;
        while (j < n) {
            int i = 0;
            boolean ok = false; //flag to check if any match found in inner loop
            int k = j; // Keep track of original j.
            while (i < m && j < n) {
                if (source.charAt(i) == target.charAt(j)) {
                    ok = true;
                    ++j;
                }
                ++i;
            }
            if (!ok) {
                return -1;
            }
            if(k==j) return -1; //check if j was moved at all during inner loop
            ++ans;
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        int ans = 0, j = 0;
        while (j < n) {
            int i = 0;
            bool ok = false; //flag to check if any match found in inner loop
            int k = j; // keep track of original j to check for progress
            while (i < m && j < n) {
                if (source[i] == target[j]) {
                    ok = true;
                    ++j;
                }
                ++i;
            }
            if (!ok) {
                return -1;
            }
            if(k==j) return -1; //check if j was moved at all during inner loop
            ++ans;
        }
        return ans;
    }
};

Go: (Similar structure to Java and C++)

func shortestWay(source string, target string) int {
	m, n := len(source), len(target)
	ans, j := 0, 0
	for j < n {
		ok := false //flag to check if any match found in inner loop
		k := j      // keep track of original j to check for progress
		for i := 0; i < m && j < n; i++ {
			if source[i] == target[j] {
				ok = true
				j++
			}
		}
		if !ok {
			return -1
		}
		if k == j { //check if j was moved at all during inner loop
			return -1
		}
		ans++
	}
	return ans
}

These examples all implement the same core algorithm with minor syntactic differences. The crucial part is the nested loop (or equivalent logic) that greedily matches characters from source to target and the condition to handle cases where a match is impossible. The k variable is added to handle the edge case where no character in the source string is able to make progress in the target string.