1055

1055. Shortest Way to Form String (Medium)

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.

Companies:
Google

Related Topics:
String, Dynamic Programming, Greedy

Similar Questions:

• Is Subsequence (Easy)
• Number of Matching Subsequences (Medium)

Solution 1. Greedy

// OJ: https://leetcode.com/problems/shortest-way-to-form-string/
// Author: github.com/lzl124631x
// Time: O(CS + T) where `C = 26` is the size of character set, and `S`/`T` is the length of `source`/`target`
// Space: O(CS)
class Solution {
public:
    int shortestWay(string source, string target) {
        int N = source.size(), M = target.size(), next[1001][26] = {};
        for (int i = 0; i < 26; ++i) {
            for (int j = N - 1, index = -1; j >= -1; --j) {
                next[j + 1][i] = index;
                if (j >= 0 && source[j] == 'a' + i) index = j + 1;
            }
        }
        int ans = 1, cur = 0;
        for (int i = 0; i < M; ++i) {
            int c = target[i] - 'a';
            if (next[0][c] == -1) return -1; // `c` doesn't exist in `source`
            if (next[cur][c] == -1) { // don't have match in this round, add a new round.
                cur = 0;
                ++ans;
            }
            cur = next[cur][c];
        }
        return ans;
    }
};

Solution 2. Binary Search

// OJ: https://leetcode.com/problems/shortest-way-to-form-string/
// Author: github.com/lzl124631x
// Time: O(S + TlogS) where `S`/`T` is the length of `source`/`target`
// Space: O(S)
class Solution {
public:
    int shortestWay(string source, string target) {
        int ans = 1, cur = -1;
        unordered_map<char, vector<int>> m; // character -> an array of indices of this character in `source`
        for (int i = 0; i < source.size(); ++i) m[source[i]].push_back(i);
        for (char c : target) {
            if (m.count(c) == 0) return -1; // `c` doesn't exist in `source`
            auto it = upper_bound(begin(m[c]), end(m[c]), cur); // the next index must be greater than the current one.
            if (it == end(m[c])) { // don't have match in this round, add a new round. 
                cur = m[c][0];
                ++ans;
            } else cur = *it;
        }
        return ans;
    }
};