Shortest Way to Form String

medium greedy two pointers string

Problem

A subsequence of a string is formed by deleting zero or more characters without changing the order of the rest. Given two strings source and target, return the minimum number of subsequences of source whose concatenation equals target. If it is impossible (target uses a character not in source), return -1.

Inputsource = "abc", target = "abcbc"

Output2

"abc" yields the subsequence "abc", then a second pass yields "bc". Together they form "abcbc".

source

target

def shortest_way(source, target):
    if not set(target) <= set(source):
        return -1
    count = 0
    j = 0
    while j < len(target):
        count += 1
        for ch in source:
            if j < len(target) and target[j] == ch:
                j += 1
    return count

function shortestWay(source, target) {
  const have = new Set(source);
  for (const ch of target) if (!have.has(ch)) return -1;
  let count = 0, j = 0;
  while (j < target.length) {
    count++;
    for (const ch of source) {
      if (j < target.length && target[j] === ch) j++;
    }
  }
  return count;
}

class Solution {
    public int shortestWay(String source, String target) {
        boolean[] have = new boolean[26];
        for (char c : source.toCharArray()) have[c - 'a'] = true;
        for (char c : target.toCharArray()) if (!have[c - 'a']) return -1;
        int count = 0, j = 0;
        while (j < target.length()) {
            count++;
            for (int k = 0; k < source.length(); k++) {
                if (j < target.length() && target.charAt(j) == source.charAt(k)) j++;
            }
        }
        return count;
    }
}

int shortestWay(string source, string target) {
    bool have[26] = {false};
    for (char c : source) have[c - 'a'] = true;
    for (char c : target) if (!have[c - 'a']) return -1;
    int count = 0, j = 0;
    while (j < (int)target.size()) {
        count++;
        for (char ch : source) {
            if (j < (int)target.size() && target[j] == ch) j++;
        }
    }
    return count;
}

Explanation

We want the fewest subsequences of source whose concatenation equals target. The greedy idea is simple: in each pass over source, grab as many of the next needed target characters as you can, then start a fresh pass for whatever is left.

First we do a quick feasibility check: if target uses any letter that source does not contain, it is impossible, so we return -1.

Otherwise we keep a pointer j into target. Each time we begin a new pass we bump count by one, then walk through source left to right; whenever source's current letter equals target[j] we advance j. One full pass over source matches the longest possible prefix of the remaining target.

Example: source = "abc", target = "abcbc". Pass 1 over abc matches a, b, c, so j reaches index 3. Pass 2 matches b, then c, finishing the target. That is 2 subsequences.

Because each pass greedily takes everything it can, we never waste a pass, so the count it returns is the minimum.

Time: O(n · m) Space: O(1)