> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/greedy/1055.-shortest-way-to-form-string.md).

# 1055. Shortest Way to Form String

From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).

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:**

* Both the `source` and `target` strings consist of only lowercase English letters from "a"-"z".
* The lengths of `source` and `target` string are between `1` and `1000`.

```cpp
// Greedy Method
int shortestWay(string source, string target) { // time: O(n * m); space: O(1)
    vector<bool> record(26, false);
    int m = source.length(), n = target.length();
    for (int i = 0; i < m; ++i) record[source[i] - 'a'] = true;
    int res = 1, j = 0; // i: position in target string; j: position in source string
    for (int i = 0; i < n; ++i) {
        if (!record[target[i] - 'a']) return -1;
        while (j < m && source[j] != target[i]) ++j;
        // if j points to m, it means no match
        if (j == m) {
            j = -1;
            ++res;
            --i;
        }
        ++j;
    }
    return res;
}
```

```cpp
// Greedy Method
int shortestWay(string source, string target) { // time: O(n * m); space: O(1)
    // i: position in target string; j: position in source string
    int i = 0, res = 0;
    while (i < target.size()) {
        int orig_idx = i;
        for (int j = 0; j < source.size(); ++j) {
            if (target[i] == source[j]) ++i;
        }
        if (i == orig_idx) return -1;
        ++res;
    }
    return res;
}
```

```cpp
// Binary Search
int shortestWay(string source, string target) { // time: O(log(m) * n); space: O(m)
    vector<vector<int> > indice(26);
    for (int j = 0; j < source.length(); ++j) indice[source[j] - 'a'].push_back(j);
    int res = 1, i = 0, j = 0;
    while (i < target.length()) {
        const vector<int>& idx = indice[target[i] - 'a'];
        if (idx.empty()) return -1;
        auto it = lower_bound(idx.begin(), idx.end(), j);
        if (it == idx.end()) {
            ++res;
            j = 0;
        } else {
            j = *it + 1;
            ++i;
        }
    }
    return res;
}
```

```cpp
// Optimized Solution with preprocess
int shortestWay(string source, string target) { // time: O(n + m); space: O(m)
    int m = source.length(), n = target.length();
    vector<vector<int> > indice(26, vector<int>(m));
    for (int j = 0; j < m; ++j) indice[source[j] - 'a'][j] = j + 1;
    for (int i = 0; i < 26; ++i) {
        for (int j = m - 1, pre = 0; j >= 0; --j) {
            if (indice[i][j] == 0) indice[i][j] = pre;
            else pre = indice[i][j];
        }
    }
    int res = 1, j = 0;
    for (int i = 0; i < n; ++i) {
        if (j == m) {
            j = 0;
            ++res;
        }
        if (indice[target[i] - 'a'][0] == 0) return -1;
        j = indice[target[i] - 'a'][j];
        if (j == 0) {
            ++res;
            --i;
        }
    }
    return res;
}
```