Minimum Number of Valid Strings to Form Target II - Solution & Explanation
Problem Statement
You are given an array of strings words and a string target.
A string x is called valid if x is a prefix of any string in words.
Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
Example 1:
Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
Output: 3
Explanation:
The target string can be formed by concatenating:
- Prefix of length 2 of
words[1], i.e."aa". - Prefix of length 3 of
words[2], i.e."bcd". - Prefix of length 3 of
words[0], i.e."abc".
Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
- Prefix of length 5 of
words[0], i.e."ababa". - Prefix of length 5 of
words[0], i.e."ababa".
Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 5 * 104- The input is generated such that
sum(words[i].length) <= 105. words[i]consists only of lowercase English letters.1 <= target.length <= 5 * 104targetconsists only of lowercase English letters.
Approach Overview
Problem Overview: You are given a list of valid strings and a target string. The goal is to form the target by concatenating valid strings (or their prefixes depending on constraints) while minimizing the total number of strings used. If the target cannot be formed, return -1. The challenge is efficiently checking which substrings of the target match valid strings while minimizing the number of segments used.
Approach 1: Dynamic Programming with Rolling Hash (O(n log n) time, O(n) space)
The core idea is to treat the problem as a segmentation task. Define dp[i] as the minimum number of valid strings required to build the prefix target[0..i). For each position, attempt to extend using any valid substring that matches the target starting at that index. Direct string comparison would be too slow, so use rolling hash to check substring equality in constant time. Precompute hashes for the target and store hashes of valid strings by length. For each index, binary search the maximum valid match length and update the DP transition. This reduces repeated comparisons and keeps substring checks efficient.
This approach combines dynamic programming for optimal substructure and string matching techniques for fast substring validation. The DP ensures minimal segmentation while rolling hash eliminates expensive character-by-character checks.
Approach 2: Greedy with Backtracking (O(n^2) worst case time, O(n) space)
A simpler approach attempts to greedily match the longest valid string starting at the current position. If multiple matches exist, choose the longest candidate and recursively attempt to build the remainder of the target. When a greedy choice fails later, backtrack and try the next candidate. Memoization can prune repeated states by caching results for each index.
This strategy works because longer matches often reduce the total number of segments. However, greedy choices are not always globally optimal, so backtracking ensures correctness. Matching can be accelerated with prefix comparisons or pre-indexed candidate lengths. Compared to the DP solution, this method is easier to implement but may degrade in performance for large inputs with many overlapping prefixes.
The greedy/backtracking strategy relies heavily on fast prefix checks and benefits from techniques like rolling hash or prefix maps for efficient substring validation.
Recommended for interviews: The dynamic programming approach with hashing is the expected optimal solution. It demonstrates understanding of segmentation DP, efficient substring matching, and complexity optimization. Explaining the greedy strategy first helps show intuition about minimizing segments, but the DP formulation proves you can guarantee the optimal result under strict constraints.
Approach 1: Dynamic Programming Approach
This approach involves using dynamic programming to determine the minimum number of valid string prefixes needed to form the target string. We define a DP array where each state represents the minimum number of prefixes required to form a prefix of the target of a given length.
We initialize a DP array to store the minimum number of prefixes required for each prefix length of the target. For each end position of a substring of the target, we check all possible starting positions. If the substring is in the set of words, we update the DP table.
Code
Python
JavaScript
C++
Complexity
Time Complexity: O(n2) where n is the length of the target string.
Space Complexity: O(n) for the DP array.
Approach 2: Greedy Approach with Backtracking
This approach leverages a backtracking strategy to identify valid prefixes greedily, trying to cut the target string into chunks from the longest valid prefix available and backtracking when necessary.
This solution uses a recursive function with backtracking to explore all possible ways to split the target into valid prefixes. It terminates on the successful attempt that minimizes the count.
Code
Python
JavaScript
Complexity
Time Complexity: Exponential in the worst case, depending on branching factors.
Space Complexity: O(m) where m is the recursion stack depth.
Approach 3: String Hashing + Binary Search + Greedy
Due to the large data scale of this problem, using the "Trie + Memoization" method will time out. We need to find a more efficient solution.
Consider starting from the i-th character of the string target and finding the maximum matching substring length, denoted as dist. For any j \in [i, i + dist - 1], we can find a string in words such that target[i..j] is a prefix of this string. This has a monotonic property, so we can use binary search to determine dist.
Specifically, we first preprocess the hash values of all prefixes of strings in words and store them in the array s grouped by prefix length. Additionally, we preprocess the hash values of target and store them in hashing to facilitate querying the hash value of any target[l..r].
Next, we design a function f(i) to represent the maximum matching substring length starting from the i-th character of the string target. We can determine f(i) using binary search.
Define the left boundary of the binary search as l = 0 and the right boundary as r = min(n - i, m), where n is the length of the string target and m is the maximum length of strings in words. During the binary search, we need to check if target[i..i+mid-1] is one of the hash values in s[mid]. If it is, update the left boundary l to mid; otherwise, update the right boundary r to mid - 1. After the binary search, return l.
After calculating f(i), the problem becomes a classic greedy problem. Starting from i = 0, for each position i, the farthest position we can move to is i + f(i). We need to find the minimum number of moves to reach the end.
We define last to represent the last moved position and mx to represent the farthest position we can move to from the current position. Initially, last = mx = 0. We traverse from i = 0. If i equals last, it means we need to move again. If last = mx, it means we cannot move further, so we return -1. Otherwise, we update last to mx and increment the answer by one.
After the traversal, return the answer.
The time complexity is O(n times log n + L), and the space complexity is O(n + L). Here, n is the length of the string target, and L is the total length of all valid strings.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n2) where n is the length of the target string. |
| Greedy Approach with Backtracking | Time Complexity: Exponential in the worst case, depending on branching factors. |
| String Hashing + Binary Search + Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Rolling Hash | O(n log n) | O(n) | Best general solution for large targets where substring comparisons must be fast |
| Greedy with Backtracking | O(n^2) worst case | O(n) | Useful when candidate matches are small or when implementing a quick recursive solution |
Video Solution
3292. Minimum Number of Valid Strings to Form Target II | Weekly Leetcode 415 | Z-Algorithm • codingMohan • 1,408 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Minimum Number of Valid Strings to Form Target II easy or hard?
Minimum Number of Valid Strings to Form Target II Python/Java solution
How to solve Minimum Number of Valid Strings to Form Target II in O(n log n)?
What is the best approach for Minimum Number of Valid Strings to Form Target II?
Is Minimum Number of Valid Strings to Form Target II asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Valid Strings to Form Target II?
What is the time complexity of Minimum Number of Valid Strings to Form Target II?
Ready to solve this problem?
Practice Minimum Number of Valid Strings to Form Target II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor