Skip to content

Practice Minimum Number of Valid Strings to Form Target I

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

Medium#3291
LeetCode Problem

Minimum Number of Valid Strings to Form Target I

Problem Statement

Build target by concatenating nonempty prefixes of the strings in words. Any prefix can be reused, and pieces may come from different words. Return the fewest pieces needed, or -1 if target cannot be formed. A substring that does not start at the beginning of a supplied word is not automatically a valid piece. Approach for version I: Build a trie from words; every non-root trie node represents a valid prefix. Let dp[i] be the fewest pieces forming target[0:i], with dp[0]=0. From each reachable i, walk forward in the trie and relax dp[j+1] after every successful character. This deterministic method uses O(sum of word lengths + target.length^2) time, appropriate for this version's 5,000-character target limit, and linear auxiliary space. Worked example: "cadecab" can be split into "ca", "de", "cab", requiring three pieces. Two pieces cannot reach its length because every available prefix has length at most three.

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

Examples

# Example 1

Input
words = ["cab","de"], target = "cadecab"
Output
3

# Example 2

Input
words = ["abc","bc"], target = "ac"
Output
-1

Constraints

words contains between 1 and 100 nonempty strings.
Each word and target contain at most 5,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 I

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

Key insight

The valid pieces are exactly the non-root nodes of a trie built from words, so from any target position a single trie walk until the first mismatch reveals every usable piece, and a dynamic program over target positions counts the fewest pieces.

Why brute force is not enough

Checking every word and every prefix length at each of up to 5,000 target positions by direct comparison costs target length times combined word length, about 5 times 10^8 character comparisons; enumerating all splits is exponential.

Approach

  1. Insert every word into a trie; each non-root node is one distinct valid prefix, merging duplicates and shared prefixes.
  2. Let state i be the fewest pieces forming the first i target characters, with state 0 equal to 0 and everything else unreachable.
  3. Go left to right. From each reachable position i, walk the trie along the target; after each successful step to depth d, the piece covering positions i through i + d - 1 is valid, so improve state i + d with state i plus one.
  4. Stop at the first character missing from the current node; since pieces are prefixes, nothing beyond a mismatch is valid. Every piece ending at a position starts earlier, so states are final by the time they are extended.
  5. Return the final state, or -1 if it stays unreachable.

Walkthrough of Example 1

words = ["cab","de"], target = "cadecab" → 3

  1. words are ["cab","de"], target is "cadecab". The trie holds c, ca, cab, d, de. State 0 is 0.
  2. From position 0 the walk matches c then a, setting states 1 and 2 to 1; the next character d is not a child of ca, so it stops.
  3. Position 1 starts with a, not a root child. From position 2 the walk matches d then e, setting states 3 and 4 to 2.
  4. Position 3 starts with e, not a root child. From position 4 the walk matches c, a, b, setting states 5, 6, 7 to 3.
  5. Positions 5 and 6 begin with a and b, neither a root child. State 7 is 3, the expected output, via ca, de, cab.

Time and space

Time O(S + T^2) · Space O(S + T). S is the combined word length and T the target length; the trie costs S to build, each of T positions walks at most T characters, and trie nodes plus the state array are linear.

Interview pitfalls

  • Treating any substring of a word as valid; only prefixes from a word's first character count.
  • Continuing past a mismatch or restarting at the root mid-walk, which invents pieces.
  • Extending from unreachable states, or initializing them to zero so they look reachable.
  • Returning the sentinel instead of -1 when the last state was never reached.
  • Using heavyweight per-node child maps that blow memory at 10^5 nodes; a fixed 26-slot array is fine.

Follow-up questions interviewers ask

  • Since valid pieces are closed under taking prefixes, can a greedy farthest-reach jump replace the dynamic program?
  • How would you handle a 50,000 character target where the quadratic walk is too slow?
  • What if each word could be used at most once?

Further reading on the technique: Trie

Related LeetCode Problems

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

Review your practice with PhantomCodeAI

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