Minimum Number of Valid Strings to Form Target I

medium trie greedy string matching

Problem

A string x is valid if it is a prefix of any word in words. Return the minimum number of valid strings that can be concatenated to form target, or -1 if it is impossible. Build a trie of all words; from each index i the longest valid piece reaches as far as the trie keeps matching target, then a greedy jump game covers target with the fewest pieces.

Inputwords = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output3

"aa" (prefix of "aaaaa") + "bcd" (prefix of "bcdef") + "abc" (prefix of "abc") = "aabcdabc", using 3 valid pieces.

words (comma-separated)

target

def min_valid_strings(words, target):
    # Build a trie: every prefix of a word is a path from the root.
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})

    n = len(target)
    # reach[i] = farthest end (exclusive) of the longest valid piece from i.
    reach = [0] * n
    for i in range(n):
        node, j = trie, i
        while j < n and target[j] in node:
            node = node[target[j]]
            j += 1
        reach[i] = j

    # Greedy jump game: fewest pieces to cover target[0..n).
    count, cur_end, farthest, i = 0, 0, 0, 0
    while cur_end < n:
        while i <= cur_end and i < n:
            farthest = max(farthest, reach[i])
            i += 1
        if farthest <= cur_end:
            return -1          # stuck before the end
        count += 1
        cur_end = farthest
    return count

function minValidStrings(words, target) {
  // Build a trie: every prefix of a word is a path from the root.
  const trie = {};
  for (const w of words) {
    let node = trie;
    for (const ch of w) node = (node[ch] ||= {});
  }

  const n = target.length;
  // reach[i] = farthest end (exclusive) of the longest valid piece from i.
  const reach = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    let node = trie, j = i;
    while (j < n && node[target[j]]) { node = node[target[j]]; j++; }
    reach[i] = j;
  }

  // Greedy jump game: fewest pieces to cover target[0..n).
  let count = 0, curEnd = 0, farthest = 0, i = 0;
  while (curEnd < n) {
    while (i <= curEnd && i < n) { farthest = Math.max(farthest, reach[i]); i++; }
    if (farthest <= curEnd) return -1;   // stuck before the end
    count++;
    curEnd = farthest;
  }
  return count;
}

int minValidStrings(String[] words, String target) {
    // Build a trie: every prefix of a word is a path from the root.
    Map<Character, Object> trie = new HashMap<>();
    for (String w : words) {
        Map<Character, Object> node = trie;
        for (char ch : w.toCharArray())
            node = (Map<Character, Object>) node.computeIfAbsent(ch, k -> new HashMap<>());
    }

    int n = target.length();
    int[] reach = new int[n];   // farthest end (exclusive) of longest piece from i
    for (int i = 0; i < n; i++) {
        Map<Character, Object> node = trie;
        int j = i;
        while (j < n && node.containsKey(target.charAt(j))) {
            node = (Map<Character, Object>) node.get(target.charAt(j));
            j++;
        }
        reach[i] = j;
    }

    // Greedy jump game: fewest pieces to cover target[0..n).
    int count = 0, curEnd = 0, farthest = 0, i = 0;
    while (curEnd < n) {
        while (i <= curEnd && i < n) farthest = Math.max(farthest, reach[i++]);
        if (farthest <= curEnd) return -1;   // stuck before the end
        count++;
        curEnd = farthest;
    }
    return count;
}

int minValidStrings(vector<string>& words, string target) {
    // Build a trie: every prefix of a word is a path from the root.
    struct Node { Node* nxt[26] = {}; };
    Node* root = new Node();
    for (auto& w : words) {
        Node* node = root;
        for (char ch : w) {
            int c = ch - 'a';
            if (!node->nxt[c]) node->nxt[c] = new Node();
            node = node->nxt[c];
        }
    }

    int n = target.size();
    vector<int> reach(n);   // farthest end (exclusive) of longest piece from i
    for (int i = 0; i < n; i++) {
        Node* node = root; int j = i;
        while (j < n && node->nxt[target[j] - 'a']) {
            node = node->nxt[target[j] - 'a'];
            j++;
        }
        reach[i] = j;
    }

    // Greedy jump game: fewest pieces to cover target[0..n).
    int count = 0, curEnd = 0, farthest = 0, i = 0;
    while (curEnd < n) {
        while (i <= curEnd && i < n) farthest = max(farthest, reach[i++]);
        if (farthest <= curEnd) return -1;   // stuck before the end
        count++;
        curEnd = farthest;
    }
    return count;
}

Explanation

A piece is valid exactly when it is a prefix of some word, so the set of all valid pieces is precisely the set of paths from the root of a trie built from words. We insert every word once; sharing prefixes keeps the trie compact.

From a position i in target, the longest valid piece we can place is found by walking the trie character by character along target[i], target[i+1], … until the trie has no matching child. The end index where we stop is reach[i] — the farthest position the single piece starting at i can cover.

Now forming target with the fewest pieces is a jump game: standing at the start of a covered prefix, any start position i inside it can extend coverage out to reach[i]. We sweep a window, track the farthest end reachable, and once we exhaust the current window we commit one more piece and jump cur_end forward to farthest.

If at any commit farthest has not moved past cur_end, no piece can cross that boundary, so target is impossible and we return -1. Otherwise the number of jumps is the minimum number of valid pieces.

Example: for target = "aabcdabc" the longest piece from index 0 covers "aa", from index 2 covers "bcd", and from index 5 covers "abc" — three greedy jumps, so the answer is 3.