How to Solve Minimum Number of Valid Strings to Form Target I

The core idea for Minimum Number of Valid Strings to Form Target I is prefix-based dynamic programming. Let dp[i] be the minimum number of valid strings needed to build the first i characters of target, then try extending from each reachable position with every prefix that matches target at that point. The interview trap is forgetting that any prefix of a word is valid, not only whole words, which changes both transitions and edge cases.

Problem Statement

You receive a list of words and a target string. A piece is usable whenever it is a prefix of at least one word in the list, so a full word can be used, but so can any shorter starting segment taken from that word.

Your goal is to concatenate the fewest such valid pieces so the final concatenation equals target exactly. If no sequence of valid prefixes can cover target from left to right without mismatch or gaps, the result is -1.

Examples

Example 1

Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output: 3

The target string can be formed by concatenating:

Example 2

Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

The target string can be formed by concatenating:

Example 3

Input: words = ["abcdef"], target = "xyz"

Output: -1

Example details omitted.

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 5 * 103
• The input is generated such that sum(words[i].length) <= 105.
• words[i] consists only of lowercase English letters.
• 1 <= target.length <= 5 * 103
• target consists only of lowercase English letters.

Solution Approach

Define the DP state on target prefixes

Set dp[i] to the minimum number of valid strings needed to form target[0:i]. Initialize dp[0] = 0 and all other states to a large value. This problem fits state transition dynamic programming because every answer for a longer prefix depends on shorter already-formed prefixes.

Transition by matching valid prefixes at each position

From each index i where dp[i] is reachable, test every word and extend as long as target matches that word starting at i. Every matched length len creates a valid piece because any prefix of the word is allowed, so update dp[i + len] = min(dp[i + len], dp[i] + 1). The key trade-off is that whole-word matching is too strict here; prefix-by-prefix extension is the actual transition rule.

Return the minimum count or detect impossibility

After processing all reachable positions, check dp[target.length]. If it was never updated, return -1. On inputs like words = ["abc","aaaaa","bcdef"] and target = "aabcdabc", the optimal build uses three pieces because greedy longer-prefix picks can still leave a worse suffix, while DP preserves the globally minimum split count.

Complexity Analysis

Let n be target.length and let L be the total length of all words. A direct DP that tries matching each word from each reachable target index runs in roughly O(n * L) in the worst case, because each transition may scan matching characters before stopping. Space is O(n) for the dp array. If you accelerate prefix checks with a trie, rolling hash, or precomputed longest matches, you reduce wasted rescans, but the state definition stays the same: minimum cost to form each target prefix.

What Interviewers Usually Probe

• They hint with dp[i] as the minimum cost for the first i target characters, which points directly to prefix DP transitions.
• They stress that a valid string is any prefix of a word, signaling that transitions are not limited to full dictionary words.
• They include impossible cases like target starting with an unseen letter, testing whether you leave unreachable DP states untouched.

Common Pitfalls or Variants

Common pitfalls

• Treating only complete words as usable pieces, which misses valid shorter prefixes and returns counts that are too high or incorrectly -1.
• Using greedy longest-prefix choices, which can trap you in a bad suffix even when a shorter current split leads to the true minimum.
• Updating dp from every index without checking reachability first, causing meaningless work and hiding why some targets are impossible.

Follow-up variants

• Build a trie over words so each target start index walks matching prefixes once instead of rescanning every word.
• Precompute the longest valid extension from each target position, then run DP or greedy-style interval expansion on those ranges.
• Change the objective from minimum number of pieces to number of ways, which keeps the same state graph but changes the DP aggregation.

How GhostInterview Helps

• GhostInterview spots that this is prefix-state DP, not word-break with whole-word membership, and steers the recurrence toward valid prefixes.
• It highlights dead positions in target where no word prefix can continue, so impossible cases become obvious before overcoding.
• It helps compare plain DP against trie-accelerated matching when repeated prefix scans are the real bottleneck in this problem.

Topic Pages

• Array
• String
• Binary Search
• Dynamic Programming
• Trie
• Segment Tree
• Rolling Hash
• String Matching
• Hash Function

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern in Minimum Number of Valid Strings to Form Target I?

The main pattern is state transition dynamic programming on target prefixes. Each dp[i] stores the fewest valid pieces needed to form the first i characters, and transitions come from every word prefix that matches target starting at i.

Why is this different from classic Word Break?

Classic Word Break usually checks membership of complete dictionary words. In LeetCode 3291, every prefix of every word is allowed, so a match of length 1, 2, 3, and so on can all be legal transitions if they match the target.

Can a greedy longest-prefix strategy solve it?

No, not safely. Taking the longest prefix at one position can force extra splits later, so this problem needs DP to compare all reachable prefix lengths and keep the global minimum.

When should I use a trie here?

A trie helps when many words share prefixes or when repeated character comparisons make the plain DP too slow. It speeds up finding all valid prefix lengths from a target index, but the answer logic still comes from the same dp state.

Why does the answer become -1 for some inputs?

The answer is -1 when no chain of valid prefixes can cover target completely. In DP terms, dp[target.length] stays unreachable because some target position cannot be entered or extended by any matching word prefix.