Problem

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.

Examples

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".

Solution

Method 1 - Greedy

To solve this problem, we need to break down the target string into subsequences of the source string. We will iterate over the target string and attempt to match its characters with those of the source string, forming subsequences.

  1. Pointer Initialization:

    • Initialize a pointer for the source (source_index) and target (target_index).
    • Initialize a counter (subseq_count) to count how many subsequences of the source are needed.

  2. Iterate Through the Target:

    • For each character in the target, check if it is present in the source starting from the current position of the source_index.
    • If a character in the target cannot be matched from the current source_index, increment subseq_count and reset the source_index to 0 to start forming a new subsequence.
    • Repeat this process until we have successfully formed the target from subsequences of the source or determine it’s impossible.

  3. Return the Result:

    • If we successfully concatenate subsequences of the source to form the target, return the subseq_count.
    • Otherwise, return -1 if the target cannot be formed.

Code

Java
public class Solution {
    public int minimumSubsequences(String source, String target) {
        int source_len = source.length();
        int target_len = target.length();
        
        int source_index = 0;
        int target_index = 0;
        int subseq_count = 0;
        
        while (target_index < target_len) {
            int start_index = target_index;
            while (source_index < source_len && target_index < target_len) {
                if (source.charAt(source_index) == target.charAt(target_index)) {
                    target_index++;
                }
                source_index++;
            }
            if (target_index == start_index) {
                return -1;
            }
            source_index = 0;
            subseq_count++;
        }
        
        return subseq_count;
    }
}
Python
class Solution:
    def minimumSubsequences(self, source: str, target: str) -> int:
        source_len = len(source)
        target_len = len(target)
        
        source_index = 0
        target_index = 0
        subseq_count = 0
        
        while target_index < target_len:
            start_index = target_index
            while source_index < source_len and target_index < target_len:
                if source[source_index] == target[target_index]:
                    target_index += 1
                source_index += 1
            if target_index == start_index:
                return -1
            source_index = 0
            subseq_count += 1
        
        return subseq_count

Complexity

  • ⏰ Time complexity: O(m * n), where m is the length of the target and n is the length of the source. This is because, in the worst case, checking each character in the target might require scanning through a majority of the source.
  • 🧺 Space complexity: O(1), since no extra space proportional to the input size is used, aside from a few pointers and counters.