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.

// 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;
}

// 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;
}

// 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;
}

// 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;
}