Minimum Number of Valid Strings to Form Target I

Med

#2922Time: O(S_W * L + n^3), where `n` is `target.length()`, `S_W` is `sum(words[i].length)`, and `L` is the max word length. Pre-computation is `O(S_W * L)`. The DP part is `O(n^3)` because of `O(n^2)` states and `O(n)` work per state for substring creation and hashing.Space: O(S_W * L + n). The hash set can store prefixes whose total length is up to `O(S_W * L)`, where `S_W` is the sum of lengths of words and `L` is the maximum word length. The DP array takes `O(n)` space.

Patterns

Dynamic Programming String Matching Rolling Hash Hash Function

Algorithms

Binary Search

Data structures

Array String Trie Segment Tree

Prompt

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 <= 100
1 <= words[i].length <= 5 * 10³
The input is generated such that sum(words[i].length) <= 10⁵.
words[i] consists only of lowercase English letters.
1 <= target.length <= 5 * 10³
target consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming combined with a hash set. We pre-compute all valid prefixes from the words array and store them in a hash set for fast lookups. Then, we use a DP array dp[i] to store the minimum number of strings to form the first i characters of the target. The DP state is updated by checking all possible last valid strings ending at each position.

Algorithm

Create a HashSet<String> to store all valid prefixes.
Iterate through each word in words, generate all its prefixes, and add them to the hash set.
Initialize a DP array dp of size target.length() + 1 with a large value, and set dp[0] = 0.
Use nested loops to iterate through all substrings target.substring(j, i).
If dp[j] is reachable and target.substring(j, i) is in the hash set, update dp[i] with min(dp[i], dp[j] + 1).
The final answer is dp[target.length()], or -1 if it's still the large value.

Walkthrough

The core of this method is the dynamic programming recurrence: dp[i] = min(dp[j] + 1) over all j < i such that target.substring(j, i) is a valid prefix. To make the check for a valid prefix efficient, we first populate a HashSet with all prefixes of every word in the input words. This pre-computation step allows us to check if any given substring is a valid prefix in approximately constant time on average (though proportional to the substring's length due to hashing).

The main DP loop then iterates through all possible end-points i of a prefix of target, and for each i, it tries all possible start-points j. If target.substring(j, i) is found in our pre-computed set, we have a potential way to form target.substring(0, i), and we update dp[i] accordingly.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public int minStrings(String[] words, String target) {7        Set<String> validPrefixes = new HashSet<>();8        for (String word : words) {9            for (int k = 1; k <= word.length(); k++) {10                validPrefixes.add(word.substring(0, k));11            }12        }13 14        int n = target.length();15        int[] dp = new int[n + 1];16        Arrays.fill(dp, Integer.MAX_VALUE);17        dp[0] = 0;18 19        for (int i = 1; i <= n; i++) {20            for (int j = 0; j < i; j++) {21                if (dp[j] != Integer.MAX_VALUE) {22                    String sub = target.substring(j, i);23                    if (validPrefixes.contains(sub)) {24                        dp[i] = Math.min(dp[i], dp[j] + 1);25                    }26                }27            }28        }29 30        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];31    }32}

Complexity

Time

O(S_W * L + n^3), where `n` is `target.length()`, `S_W` is `sum(words[i].length)`, and `L` is the max word length. Pre-computation is `O(S_W * L)`. The DP part is `O(n^3)` because of `O(n^2)` states and `O(n)` work per state for substring creation and hashing.

Space

O(S_W * L + n). The hash set can store prefixes whose total length is up to `O(S_W * L)`, where `S_W` is the sum of lengths of words and `L` is the maximum word length. The DP array takes `O(n)` space.

Trade-offs

Pros

Conceptually simpler than using a Trie.
Straightforward implementation of the DP recurrence.

Cons

High time complexity makes it too slow for the given constraints.
High space complexity if words are long and numerous.

This optimized approach uses dynamic programming with a Trie (prefix tree). Instead of a hash set, a Trie is built from all the words in words. This data structure is ideal for prefix-based searches. The DP logic is enhanced: for each position i in the target, we traverse the Trie with subsequent characters target[j] (j >= i). Each time we find a valid prefix in the Trie, we update the DP state for the corresponding end position j+1.

Algorithm

Define a TrieNode class.
Build a Trie by inserting all words from the words array.
Initialize a DP array dp of size target.length() + 1 with a large value, and set dp[0] = 0.
Iterate i from 0 to n-1. If dp[i] is reachable:
- Start a traversal from the Trie root.
- Iterate j from i to n-1, traversing the Trie with target.charAt(j).
- If the path is valid, update dp[j+1] with min(dp[j+1], dp[i] + 1).
- If the path breaks, stop the inner traversal.
The final answer is dp[target.length()], or -1 if it's unreachable.

Walkthrough

This method significantly improves performance by replacing the hash set with a Trie. A Trie stores the dictionary of words in a way that all prefixes can be checked efficiently. We first insert all words from the words array into the Trie.

Then, we apply dynamic programming. We iterate through the target string with an index i. If dp[i] is reachable (not infinity), it means we have successfully formed target.substring(0, i). From this point, we try to extend our solution by finding the next valid string. We do this by starting a search from the Trie's root with characters target[i], target[i+1], .... For every character target[j] that corresponds to a valid path in the Trie, we know target.substring(i, j+1) is a valid prefix. This allows us to update dp[j+1] with dp[i] + 1. This avoids the expensive substring creation and hashing at each step of the inner loop.

1import java.util.Arrays;2 3class Solution {4    class TrieNode {5        TrieNode[] children = new TrieNode[26];6    }7 8    public int minStrings(String[] words, String target) {9        TrieNode root = new TrieNode();10        for (String word : words) {11            TrieNode curr = root;12            for (char c : word.toCharArray()) {13                if (curr.children[c - 'a'] == null) {14                    curr.children[c - 'a'] = new TrieNode();15                }16                curr = curr.children[c - 'a'];17            }18        }19 20        int n = target.length();21        int[] dp = new int[n + 1];22        Arrays.fill(dp, Integer.MAX_VALUE);23        dp[0] = 0;24 25        for (int i = 0; i < n; i++) {26            if (dp[i] == Integer.MAX_VALUE) {27                continue;28            }29            30            TrieNode curr = root;31            for (int j = i; j < n; j++) {32                char c = target.charAt(j);33                if (curr.children[c - 'a'] == null) {34                    break; // Not a valid prefix35                }36                curr = curr.children[c - 'a'];37                // Since any prefix is valid, we can make a cut here38                dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);39            }40        }41 42        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];43    }44}

Complexity

Time

O(S_W + n^2), where `n` is `target.length()` and `S_W` is `sum(words[i].length)`. Building the Trie is `O(S_W)`. The DP calculation is `O(n^2)` due to the nested loops with constant time work inside.

Space

O(S_W + n). The Trie requires `O(S_W)` space, where `S_W` is the sum of lengths of all words. The DP array takes `O(n)` space.

Trade-offs

Pros

Highly efficient with O(n^2) time complexity, suitable for the given constraints.
Trie is the optimal data structure for prefix-based problems.

Cons

Requires implementation of a Trie data structure, which adds some complexity.

Solutions

Solution

1class Trie { Trie [] children = new Trie [ 26 ]; void insert ( String w ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] == null ) { node . children [ j ] = new Trie (); } node = node . children [ j ]; } } } class Solution { private Integer [] f ; private char [] s ; private Trie trie ; private final int inf = 1 << 30 ; public int minValidStrings ( String [] words , String target ) { trie = new Trie (); for ( String w : words ) { trie . insert ( w ); } s = target . toCharArray (); f = new Integer [ s . length ]; int ans = dfs ( 0 ); return ans < inf ? ans : - 1 ; } private int dfs ( int i ) { if ( i >= s . length ) { return 0 ; } if ( f [ i ] != null ) { return f [ i ]; } Trie node = trie ; f [ i ] = inf ; for ( int j = i ; j < s . length ; ++ j ) { int k = s [ j ] - 'a' ; if ( node . children [ k ] == null ) { break ; } f [ i ] = Math . min ( f [ i ], 1 + dfs ( j + 1 )); node = node . children [ k ]; } return f [ i ]; } }

1class Trie { public: Trie * children [ 26 ]{}; void insert ( string & word ) { Trie * node = this ; for ( char & c : word ) { int i = c - 'a' ; if ( ! node -> children [ i ]) { node -> children [ i ] = new Trie (); } node = node -> children [ i ]; } } }; class Solution { public: int minValidStrings ( vector < string >& words , string target ) { int n = target . size (); Trie * trie = new Trie (); for ( auto & w : words ) { trie -> insert ( w ); } const int inf = 1 << 30 ; int f [ n ]; memset ( f , - 1 , sizeof ( f )); auto dfs = [ & ]( auto && dfs , int i ) -> int { if ( i >= n ) { return 0 ; } if ( f [ i ] != - 1 ) { return f [ i ]; } f [ i ] = inf ; Trie * node = trie ; for ( int j = i ; j < n ; ++ j ) { int k = target [ j ] - 'a' ; if ( ! node -> children [ k ]) { break ; } node = node -> children [ k ]; f [ i ] = min ( f [ i ], 1 + dfs ( dfs , j + 1 )); } return f [ i ]; }; int ans = dfs ( dfs , 0 ); return ans < inf ? ans : - 1 ; } };

1def min ( a : int , b : int ) -> int : return a if a < b else b class Trie : def __init__ ( self ): self . children : List [ Optional [ Trie ]] = [ None ] * 26 def insert ( self , w : str ): node = self for i in map ( lambda c : ord ( c ) - 97 , w ): if node . children [ i ] is None : node . children [ i ] = Trie () node = node . children [ i ] class Solution : def minValidStrings ( self , words : List [ str ], target : str ) -> int : @ cache def dfs ( i : int ) -> int : if i >= n : return 0 node = trie ans = inf for j in range ( i , n ): k = ord ( target [ j ]) - 97 if node . children [ k ] is None : break node = node . children [ k ] ans = min ( ans , 1 + dfs ( j + 1 )) return ans trie = Trie () for w in words : trie . insert ( w ) n = len ( target ) ans = dfs ( 0 ) return ans if ans < inf else - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem