1055. Shortest Way to Form String

Problem Description

The problem involves finding how to form a given target string by concatenating subsequences of a source string. A subsequence can be obtained by deleting zero or more characters from a string without changing the order of the remaining characters. We need to determine the minimum number of these subsequences from source needed to create the target string. If it's not possible to form the target from subsequences of source, the function should return -1.

To visualize the problem, think about how you can create the word "cat" using letters from the word "concentrate". You can select c, omit o, pick a, skip n, c, e, n, and then pick t and skip r, a, t, e. That forms one subsequence "cat". Moreover, if you had a target like "catat", you'd need two subsequences from "concentrate" to form it—"cat" and "at".

Intuition

The intuition for the solution is built on the idea that we can iterate over the source and target strings simultaneously, matching characters from target and moving through source. We do this in a loop that continues until we've either created the target string or determined it's impossible.

For each iteration (which corresponds to constructing a single subsequence), we do the following:

1. Start from the beginning of the source string and look for a match for the current character in target.
2. Each time we find a match, we move to the next character in target but continue searching from the current position in source.
3. If we reach the end of the source without finding the next character in target, we start over from the beginning of source and increment our subsequence count.
4. If when restarting the source string we don't make any progress in target (meaning we didn't find even the next character in the target), we conclude that the target cannot be formed and return -1.

The concept is similar to using multiple copies of the source string side by side, and crossing out characters as we match them to target. Whenever we reach the end of a source string copy and still have characters left to match in target, we move on to the next copy of source, symbolizing this with an increment in our subsequence counter. This continues until we've matched the entire target string or have verified that it's impossible.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The solution uses a two-pointer technique to iterate through both the source and target strings. One pointer (i) traverses the source string, while the other pointer (j) iterates over the target string. Here's a step-by-step breakdown of the key components of the algorithm:

1. Function f(i, j): This is a helper function that takes two indices, i for the source and j for the target. The purpose of f is to try to match as many characters of target starting from index j with the source starting from index i until we reach the end of source. The function runs a while loop until either i or j reaches the end of their respective strings. Inside this loop:

   • If the characters at source[i] and target[j] match, increment j to check for the next character in target.
   • Whether or not there is a match, always increment i because we can skip characters in source.
   • The function returns the updated index j after traversing through source.

2. Main Algorithm: Once we have our helper function, the main algorithm proceeds as follows:

   • We initialize two variables, m and n as the lengths of source and target respectively, and ans and j to keep track of the number of subsequences needed and the current index in target.
   • We use a while loop that continues as long as j < n, meaning there are still characters in target that have not been matched.
   • Inside the while loop, we call our helper function f(0, j) which tries to match target starting from the current j index with source starting from 0. If the returned index k is the same as j, it means no further characters from target could be matched and we return -1 as it's impossible to form target.
   • If k is different from j, this means we've managed to match some part of target, and we update j to k and increment ans to signify the creation of another subsequence from source.
   • The process repeats until all characters of target are matched.

3. Return Value: The loop ends with two possibilities; either we were able to form target successfully, hence we return the ans which is the count of subsequences needed, or we determined that target cannot be formed from source and returned -1.

Complexity Analysis

• Time Complexity: O(m * n), where m is the length of source and n is the length of target. In the worst case, we iterate through the entire source for every character in target.
• Space Complexity: O(1), we only use a fixed amount of extra space for the pointers and the ans variable regardless of the input size.

By thoroughly understanding the definition of a subsequence and carefully managing the iteration through both strings, this solution efficiently determines the minimum number of subsequences of source required to form target or establishes that it's not possible.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example:

• source: "abcab"
• target: "abccba"

Walkthrough:

1. Initialize the count of subsequences (ans) needed to 0 and the index j in the target to 0.

2. Since j < n (where n is the length of target), start the iteration and call the helper function f with f(0, 0).

3. Inside f(0, 0), iterate over source and target. For each character in source, check if it matches the current target[j].

   • For source[0] = 'a' and target[0] = 'a', there's a match, increment j to 1 (next character in target).
   • Continue to source[1] = 'b', which matches target[1] = 'b', increment j to 2.
   • Continue to source[2] = 'c', which matches target[2] = 'c', increment j to 3.
   • The character source[3] = 'a' does not match target[3] = 'c', so just increment i.
   • The character source[4] = 'b' does not match target[3] either, increment i again and now i reaches the end of source.

4. The f function returns j which is now 3. Since j has increased from 0 to 3, one subsequence "abc" has been matched from source.

   • Increment ans to 1 and start matching the next subsequence with f(0, 3).

5. In the second call to f(0, 3), we iterate from the start of source again:

   • Skip source[0] = 'a', since it doesn't match target[3] = 'c'.
   • Skip source[1] = 'b', since it doesn't match target[3] either.
   • source[2] matches target[3], so increment j to 4.
   • source[3] matches target[4], increment j to 5.
   • No more characters in source match target[5] = 'a', but once we reach the end of source, f returns j which is now 5.

6. Increment ans to 2 and start matching the last character with f(0, 5).

7. In the third call to f(0, 5), the first character source[0] = 'a' matches the last character target[5] = 'a'. The j is incremented to 6, which is the length of target, so the entire target string has been matched.

8. Increment ans to 3 which is our final answer.

Return:

The function would return 3 as it takes three subsequences of source to form the target string "abccba".

This example collapses the entire iteration into a concise explanation, demonstrating how the algorithm works in practice and matches subsequences in the source to form the target string.

Solution Implementation

Time and Space Complexity

Time Complexity

The primary function of the algorithm, shortestWay, iterates over the target string while repeatedly scanning the source string to find subsequences that match the target. The function f(i, j) is called for each subsequence found and runs in a while loop that continues until either the end of the source or target string is reached. The worst-case scenario occurs when every character in the source has to be visited for every character in the target.

Given:

• m is the length of source
• n is the length of target

The worst-case time complexity can be roughly bounded by O(n * m) since, in the worst case, the substring search could traverse the entire source string for each character in the target string.

Space Complexity

The space complexity of the algorithm is O(1) as it only uses a fixed number of integer variables m, n, ans, j, and k, and does not allocate any additional space proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.