Skip to content

Practice Minimum Number of Valid Strings to Form Target II

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3292
LeetCode Problem

Minimum Number of Valid Strings to Form Target II

Problem Statement

A usable piece is any nonempty prefix of any word in words. Pieces can be reused. Find the fewest pieces whose concatenation equals target exactly, returning -1 when no construction exists. This larger version allows a 50,000-character target, so repeatedly walking a trie from every target position can be too slow. Approach for version II: For each word, run a KMP prefix-function scan over word + separator + target. At each target endpoint, retain the longest word-prefix match over all words. Let L[i] be that maximum length ending at i-1. Then dp[0]=0 and dp[i]=1+dp[i-L[i]] when L[i]>0 and the earlier state is reachable; otherwise it is unreachable. The longest suffix is optimal because valid pieces are prefix-closed, so reaching a shorter target prefix never requires more pieces. Time: O(sum of word lengths + words.length*target.length); auxiliary space is linear. Worked example: "abcabc" uses the prefix "abc" twice from "abcd", giving two pieces. "xyxq" is impossible with only prefixes of "xyz" because q never appears in any available piece.

Source: Minimum Number of Valid Strings to Form Target II on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
words = ["abcd","bc"], target = "abcabc"
Output
2

# Example 2

Input
words = ["xyz"], target = "xyxq"
Output
-1

Constraints

words contains between 1 and 100 nonempty strings.
Each word and target contain at most 50,000 characters.
The combined word lengths do not exceed 100,000.
target is nonempty; every input character is a lowercase English letter.

How to solve Minimum Number of Valid Strings to Form Target II

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Valid pieces are closed under shortening, so the fewest pieces for a target prefix never decreases as the prefix grows. That means the last piece should always be the longest suffix of the current prefix that is a word prefix, and a KMP failure function per word yields that length for free.

Why brute force is not enough

Walking a trie from every target position, as in the smaller version, costs about target length squared, roughly 2.5 times 10^9 steps for a 50,000 character target.

Approach

  1. For each word, form word, a separator absent from both inputs, then target, and compute its prefix function. The separator stops any match from crossing into the word, so the value at a target index is the longest suffix of target ending there that is a prefix of this word.
  2. Take the maximum over all words at each index to get L[i], the longest valid piece ending at position i - 1. Process one word at a time so only one failure array is alive.
  3. Define the state for prefix length i as the fewest pieces forming it, with the empty prefix at 0. If a prefix of length j is formed with m pieces, trimming the last piece forms every shorter prefix with at most m pieces, so states are nondecreasing and every length up to the largest reachable one is reachable.
  4. Set each state to one plus the state at i - L[i] when L[i] is positive and that state is reachable; by monotonicity no shorter last piece does better. If L[i] is zero the prefix is unreachable.
  5. Return the final state, or -1 if unreachable.

Walkthrough of Example 1

words = ["abcd","bc"], target = "abcabc" → 2

  1. words are ["abcd","bc"], target is "abcabc". Valid pieces are a, ab, abc, abcd, b, bc.
  2. Longest valid suffix per prefix length: L[1] = 1 (a), L[2] = 2 (ab), L[3] = 3 (abc), L[4] = 1 (a), L[5] = 2 (ab), L[6] = 3 (abc).
  3. Lengths 1, 2, 3 each cost 1 piece because they jump back to length 0.
  4. Length 4 costs 1 + state(3) = 2, length 5 costs 1 + state(3) = 2, length 6 costs 1 + state(3) = 2.
  5. The final state is 2, matching the expected output with pieces abc and abc.

Time and space

Time O(S + W * T) · Space O(T + M). S is the combined word length, W the word count, T the target length, and M the longest word; each word's pass costs its length plus T, and only one combined array of size M + T plus the L and state arrays exist at once.

Interview pitfalls

  • Omitting the separator or using a lowercase letter for it, which lets matches spill from the word into the target.
  • Reusing the version I trie walk; at 50,000 characters the quadratic behavior times out.
  • Taking a shorter suffix than the longest; the optimality argument depends on the longest.
  • Allocating the concatenation for all words at once instead of sequentially, which can exhaust memory.
  • Confusing a matched length at index i with a piece starting at i; the prefix function describes pieces ending at i.

Follow-up questions interviewers ask

  • Can you instead use a Z-function for longest matches starting at each position, then a greedy jump-game pass?
  • How would rolling hashes plus binary search on piece length compare in speed and correctness risk?
  • What if the pieces had to be suffixes of words rather than prefixes?

Further reading on the technique: Knuth-Morris-Pratt algorithm

Related LeetCode Problems

Practice more problems similar to Minimum Number of Valid Strings to Form Target II.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.