1055. Shortest Way to Form String

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

Example 1:

Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".

Example 2:

Input: source = "abc", target = "acdbc"
Output: -1
Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.

Example 3:

Input: source = "xyz", target = "xzyxz"
Output: 3
Explanation: The target string can be constructed as follows "xz" + "y" + "xz".

Constraints:

• 1 <= source.length, target.length <= 1000

• source and target consist of lowercase English letters.

Solution

My first idea is to use backtrack to check any permutations and find the minimum concatenation count. If the beginning of the target string (ex, target[o, i]) is the subsequence of the source. then we can reduce the scope of the problem to solving the count of remained target ex. ( string [i+1... end]).

However, it is not that efficient, because we don't need to check every substring of the target's string. We can just try to cover the target's characters by source string as many as possible in one concatenation. And the rest of the part is the same as my first idea.

public int shortestWay(String source, String target) {
    int ans = helper(source.toCharArray(), target.toCharArray(), 0);
    return ans;
}

public int helper(char[] src, char[] target, int index) {
    if(index >= target.length) return 0;
    int i = index;
    for(int j = 0; j < src.length && i < target.length; j++) {
        if(src[j] == target[i]){
            i++;
        }
    }
    if(i == index) return -1;
    int temp = helper(src, target, i);
    if(temp == -1) return -1;
    return 1 + temp;
}