# 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]).  &#x20;

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.

```java
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;
}

```
