Leetcode 1055. Shortest Way to Form String

Problem:

In this problem, we have 2 strings - the 'source' string and the 'target' string. We can form a subsequence from the source string by deleting some number of characters (including possibly none). We need to find out the minimum number of such subsequences of the source string, the concatenation of which equals the target string. If it's not possible to form the target string from the subsequences of the source string, return -1.

Example:

Consider a case where source string is "abc" and target string is "abcbc". Here, we can form a target string by concatenating two subsequences of the source string - "abc" and "bc". Hence, the output for this case would be 2.

Another example is of source string "abc" and target string "acdbc". Here, as the target string contains the character 'd' which is not present in the source string, it's not possible to form the target string from the subsequences of source string. Hence, return -1 for this case.

Solution Approach:

This problem can be approached by using a two-pointer approach where we increment the source pointer when the current character of the target string matches the source string. We increment the target pointer no matter if the current character can be found in the source string or not.

Python Solution:

1
2Python
3class Solution:
4  def shortestWay(self, source, target):
5    ans = 0
6
7    i = 0
8    while i < len(target):
9      j = 0
10      prevIndex = i
11      while j < len(source):
12        if i < len(target) and source[j] == target[i]:
13          i += 1
14        j += 1
15      if i == prevIndex:
16        return -1
17      ans += 1
18
19    return ans

Here, we iterate over the entire target string (outer loop), and for every character in the target string (target[i]), we check if it can be found in the source string (inner loop). If we find a match (source[j] == target[i]), we increment both i and j. If we don’t find a match, we just increment j. After the inner loop ends, if i is still equal to prevIndex (which means not a single character of source string could match with target[i]), we return -1 a there is no subsequence of source that can form target string. If not, we increment ans. After the outer loop ends, ans will be the minimum number of subsequences of source that can form target.

Java Solution:

1
2Java
3class Solution {
4  public int shortestWay(String source, String target) {
5    int ans = 0;
6
7    int i = 0;
8    while (i < target.length()) {
9      int j = 0;
10      int prevIndex = i;
11      while (j < source.length()) {
12        if (i < target.length() && source.charAt(j) == target.charAt(i)) {
13          i++;
14        }
15        j++;
16      }
17      if (i == prevIndex) {
18        return -1;
19      }
20      ans++;
21    }
22
23    return ans;
24  }
25}

JavaScript Solution:

1
2JavaScript
3class Solution {
4  shortestWay(source, target) {
5    let ans = 0;
6
7    let i = 0;
8    while (i < target.length) {
9      let j = 0;
10      let prevIndex = i;
11      while (j < source.length) {
12        if (i < target.length && source[j] === target[i]) {
13          i++;
14        }
15        j++;
16      }
17      if (i === prevIndex) {
18        return -1;
19      }
20      ans++;
21    }
22
23    return ans;
24  }
25}

C++ Solution:

1
2C++
3class Solution {
4  public:
5    int shortestWay(string source, string target) {
6      int ans = 0;
7
8      int i = 0;
9      while (i < target.size()) {
10        int j = 0;
11        int prevIndex = i;
12        while (j < source.size()) {
13          if (i < target.size() && source[j] == target[i]) {
14            i++;
15          }
16          j++;
17        }
18        if (i == prevIndex) {
19          return -1;
20        }
21        ans++;
22      }
23
24      return ans;
25    }
26};

C# Solution:

1
2Csharp
3public class Solution {
4  public int ShortestWay(string source, string target) {
5    int ans = 0;
6
7    int i = 0;
8    while (i < target.Length) {
9      int j = 0;
10      int prevIndex = i;
11      while (j < source.Length) {
12        if (i < target.Length && source[j] == target[i]) {
13          i++;
14        }
15        j++;
16      }
17      if (i == prevIndex) {
18        return -1;
19      }
20      ans++;
21    }
22
23    return ans;
24  }
25}

Conclusion:

The solutions above run in O(n*m) time complexity, where n is the length of the target string and m is the length of the source string. This is because for every character in the target string, we are iterating over the entire source string.

In addition, the space complexity for these methods is O(1) since we are not using any additional space that grows with input size. To improve the performance further, preprocessing steps such as creating a hash map or list for each character in the source string with indices of its occurrence can be considered. This data structure can then be used to quickly locate the characters of the target string in the source string, skipping unnecessary iterations.

However, the above solutions are both simple and efficient for typical use cases. They clearly demonstrate the power of the two-pointer method to solve this string subsequence problem, and they also provide efficient, easy-to-understand code in multiple languages.

Whether you take the preprocessing approach or the direct, two-pointers approach, programming problems like this one are a great opportunity to get comfortable with manipulating strings and understanding underlying algorithm and data structure concepts. So get out there, start coding, and have fun solving problems like these. Remember that the process of problem-solving is just as important as the final solution itself, and practice makes perfect!