Minimum Number of Valid Strings to Form Target II

Hard

#2923Time: O(n³ * m * L_avg), where `n` is `target.length`, `m` is `words.length`, and `L_avg` is the average length of a word. The nested loops for `i` and `j` give `O(n²)`, substring extraction can take `O(n)`, and the validity check takes `O(m * L_avg)`. A tighter bound is `O(n² * S)` where S is the total length of all words, as `sum(check_time) = sum(m*len(sub))`, which is dominated by `O(S)` for each `(i,j)` pair. A simple analysis gives `O(n^3 * m)`.Space: O(n), where `n` is the length of the `target` string. This is for the `dp` array.

Patterns

Dynamic Programming String Matching Rolling Hash Hash Function

Algorithms

Binary Search

Data structures

Array String 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 to solve the problem. We define dp[i] as the minimum number of valid strings required to form the prefix of target of length i. The goal is to compute dp[n], where n is the length of target.

The base case is dp[0] = 0, as an empty string requires zero valid strings. For each i from 1 to n, we try to find a split point j (where 0 <= j < i) such that the substring target[j...i-1] is a valid prefix. If it is, we can potentially form target[0...i-1] by taking an optimal solution for target[0...j-1] (which is dp[j]) and adding one more valid string, target[j...i-1].

To check if target[j...i-1] is a valid prefix, we perform a naive search: iterate through every word in the words array and use the startsWith method. We take the minimum over all possible split points j.

Algorithm

Let n be the length of the target string.
Create a dynamic programming array dp of size n + 1. dp[i] will store the minimum number of valid strings to form the prefix target[0...i-1].
Initialize dp[0] = 0 (an empty prefix requires 0 strings) and all other dp[i] to a value representing infinity (e.g., n + 1).
Iterate from i = 1 to n: a. For each i, iterate from j = 0 to i - 1. b. Extract the substring sub = target.substring(j, i). c. Check if sub is a valid prefix. This is done by iterating through every word in the words array and checking if word.startsWith(sub). d. If sub is a valid prefix and dp[j] is not infinity, it means we can form target[0...i-1] by appending sub to a valid formation of target[0...j-1]. Update dp[i] = min(dp[i], dp[j] + 1).
After the loops complete, if dp[n] is still infinity, it's impossible to form the target. Return -1.
Otherwise, dp[n] holds the minimum number of strings, so return dp[n].

Walkthrough

The algorithm iterates through all possible ending positions i in the target string and for each i, it considers all possible starting positions j. The substring between j and i is then checked for validity. This validity check is the main performance bottleneck, as it involves iterating through the entire words array for every single substring. This leads to a very high polynomial time complexity.

1public int minStrings(String[] words, String target) {2    int n = target.length();3    int[] dp = new int[n + 1];4    java.util.Arrays.fill(dp, n + 1);5    dp[0] = 0;6 7    for (int i = 1; i <= n; i++) {8        for (int j = 0; j < i; j++) {9            if (dp[j] > n) {10                continue;11            }12            String sub = target.substring(j, i);13            boolean is_valid = false;14            for (String word : words) {15                if (word.startsWith(sub)) {16                    is_valid = true;17                    break;18                }19            }20 21            if (is_valid) {22                dp[i] = Math.min(dp[i], dp[j] + 1);23            }24        }25    }26 27    return dp[n] > n ? -1 : dp[n];28}

Complexity

Time

O(n³ * m * L_avg), where `n` is `target.length`, `m` is `words.length`, and `L_avg` is the average length of a word. The nested loops for `i` and `j` give `O(n²)`, substring extraction can take `O(n)`, and the validity check takes `O(m * L_avg)`. A tighter bound is `O(n² * S)` where S is the total length of all words, as `sum(check_time) = sum(m*len(sub))`, which is dominated by `O(S)` for each `(i,j)` pair. A simple analysis gives `O(n^3 * m)`.

Space

O(n), where `n` is the length of the `target` string. This is for the `dp` array.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons

Extremely inefficient due to repeated and slow prefix checks.
The time complexity makes it infeasible for the given constraints, leading to a Time Limit Exceeded (TLE) error.

This approach significantly optimizes the prefix checking part of the previous solution by using a Trie (Prefix Tree). A Trie is an ideal data structure for storing a dictionary of strings and efficiently checking for prefixes.

First, we build a Trie and insert all the strings from the words array. Since any prefix of a word in words is a valid string, any path from the root of our Trie represents a valid string. This preprocessing step takes time proportional to the total number of characters in all words.

Next, we use the same dynamic programming setup as before: dp[i] stores the minimum number of strings to form target[0...i-1]. When computing the transitions, instead of naively checking for valid prefixes, we traverse the Trie. For each starting position i in the target, we see how far we can match target[i...] in the Trie. For every match target[i...j], we update the dp state for the new prefix target[0...j]. This avoids the costly iteration over the words array for every substring.

Algorithm

Preprocessing: Build a Trie data structure. Insert every string from the words array into the Trie. Any path from the root of the Trie represents a valid prefix.
Initialization: Let n be the length of target. Create a dp array of size n + 1, where dp[i] is the minimum strings for target[0...i-1]. Initialize dp[0] = 0 and other elements to infinity (e.g., n + 1).
Dynamic Programming: Iterate i from 0 to n - 1: a. If dp[i] is infinity, it means the prefix target[0...i-1] cannot be formed, so we can't extend from it. Continue to the next i. b. If dp[i] is reachable, start a traversal from the root of the Trie. Iterate j from i to n - 1. c. In each step of the inner loop, advance in the Trie using target.charAt(j). d. If the traversal hits a dead end (null child), it means target[i...j] and any longer string starting at i cannot be a valid prefix. Break the inner loop. e. If the traversal is successful, target[i...j] is a valid prefix. We can form target[0...j] in dp[i] + 1 strings. Update dp[j + 1] = min(dp[j + 1], dp[i] + 1).
Result: After the loops, if dp[n] is infinity, return -1. Otherwise, return dp[n].

Walkthrough

The core of this method is the synergy between DP and the Trie. The Trie allows us to find all valid prefixes starting at a given position i in target efficiently. Instead of re-checking from scratch for every potential substring, we perform a single traversal from i outwards.

1class TrieNode {2    TrieNode[] children = new TrieNode[26];3}4 5class Trie {6    TrieNode root = new TrieNode();7 8    public void insert(String word) {9        TrieNode curr = root;10        for (char c : word.toCharArray()) {11            int index = c - 'a';12            if (curr.children[index] == null) {13                curr.children[index] = new TrieNode();14            }15            curr = curr.children[index];16        }17    }18}19 20public int minStrings(String[] words, String target) {21    Trie trie = new Trie();22    int maxWordLength = 0;23    for (String word : words) {24        trie.insert(word);25        maxWordLength = Math.max(maxWordLength, word.length());26    }27 28    int n = target.length();29    int[] dp = new int[n + 1];30    java.util.Arrays.fill(dp, n + 1);31    dp[0] = 0;32 33    for (int i = 0; i < n; i++) {34        if (dp[i] > n) {35            continue;36        }37 38        TrieNode curr = trie.root;39        // The inner loop will naturally break after at most maxWordLength iterations40        // because any valid prefix cannot be longer than the longest word.41        for (int j = i; j < n; j++) {42            int index = target.charAt(j) - 'a';43            if (curr.children[index] == null) {44                break;45            }46            curr = curr.children[index];47            // target.substring(i, j + 1) is a valid prefix48            dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);49        }50    }51 52    return dp[n] > n ? -1 : dp[n];53}

Complexity

Time

O(S + n * L_max), where `S` is the total length of strings in `words`, `n` is `target.length`, and `L_max` is the maximum length of a word. `O(S)` is for building the Trie. The DP calculation involves an outer loop of `O(n)` and an inner loop that, for each `i`, traverses the Trie. The depth of this traversal is at most `L_max`. In the worst case, this can be `O(n²)`, but it's bounded by `n * L_max`.

Space

O(S + n), where `S` is the sum of the lengths of all strings in `words` and `n` is the length of `target`. `O(S)` is for the Trie and `O(n)` is for the `dp` array.

Trade-offs

Pros

Much more efficient than the naive approach.
The use of a Trie for prefix lookups is optimal.
Handles the given constraints effectively in most cases.

Cons

The worst-case time complexity can still be high if the maximum word length (L_max) and target length (n) are both large.
Requires implementation of a Trie data structure.

Solutions

Solution

1class Hashing { private final long [] p ; private final long [] h ; private final long mod ; public Hashing ( String word , long base , int mod ) { int n = word . length (); p = new long [ n + 1 ]; h = new long [ n + 1 ]; p [ 0 ] = 1 ; this . mod = mod ; for ( int i = 1 ; i <= n ; i ++) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word . charAt ( i - 1 )) % mod ; } } public long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } } class Solution { private Hashing hashing ; private Set < Long >[] s ; public int minValidStrings ( String [] words , String target ) { int base = 13331 , mod = 998244353 ; hashing = new Hashing ( target , base , mod ); int m = Arrays . stream ( words ). mapToInt ( String: : length ). max (). orElse ( 0 ); s = new Set [ m + 1 ]; Arrays . setAll ( s , k -> new HashSet <>()); for ( String w : words ) { long h = 0 ; for ( int j = 0 ; j < w . length (); j ++) { h = ( h * base + w . charAt ( j )) % mod ; s [ j + 1 ]. add ( h ); } } int ans = 0 ; int last = 0 ; int mx = 0 ; int n = target . length (); for ( int i = 0 ; i < n ; i ++) { int dist = f ( i , n , m ); mx = Math . max ( mx , i + dist ); if ( i == last ) { if ( i == mx ) { return - 1 ; } last = mx ; ans ++; } } return ans ; } private int f ( int i , int n , int m ) { int l = 0 , r = Math . min ( n - i , m ); while ( l < r ) { int mid = ( l + r + 1 ) >> 1 ; long sub = hashing . query ( i + 1 , i + mid ); if ( s [ mid ]. contains ( sub )) { l = mid ; } else { r = mid - 1 ; } } return l ; } }

1class Hashing { private: vector < long long > p ; vector < long long > h ; long long mod ; public: Hashing ( const string & word , long long base , int mod ) { int n = word . size (); p . resize ( n + 1 ); h . resize ( n + 1 ); p [ 0 ] = 1 ; this -> mod = mod ; for ( int i = 1 ; i <= n ; i ++ ) { p [ i ] = ( p [ i - 1 ] * base ) % mod ; h [ i ] = ( h [ i - 1 ] * base + word [ i - 1 ]) % mod ; } } long long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } }; class Solution { public: int minValidStrings ( vector < string >& words , string target ) { int base = 13331 , mod = 998244353 ; Hashing hashing ( target , base , mod ); int m = 0 , n = target . size (); for ( const string & word : words ) { m = max ( m , ( int ) word . size ()); } vector < unordered_set < long long >> s ( m + 1 ); for ( const string & w : words ) { long long h = 0 ; for ( int j = 0 ; j < w . size (); j ++ ) { h = ( h * base + w [ j ]) % mod ; s [ j + 1 ]. insert ( h ); } } auto f = [ & ]( int i ) -> int { int l = 0 , r = min ( n - i , m ); while ( l < r ) { int mid = ( l + r + 1 ) >> 1 ; long long sub = hashing . query ( i + 1 , i + mid ); if ( s [ mid ]. count ( sub )) { l = mid ; } else { r = mid - 1 ; } } return l ; }; int ans = 0 , last = 0 , mx = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int dist = f ( i ); mx = max ( mx , i + dist ); if ( i == last ) { if ( i == mx ) { return - 1 ; } last = mx ; ans ++ ; } } return ans ; } };

1class Hashing : __slots__ = [ "mod" , "h" , "p" ] def __init__ ( self , s : List [ str ], base : int , mod : int ): self . mod = mod self . h = [ 0 ] * ( len ( s ) + 1 ) self . p = [ 1 ] * ( len ( s ) + 1 ) for i in range ( 1 , len ( s ) + 1 ): self . h [ i ] = ( self . h [ i - 1 ] * base + ord ( s [ i - 1 ])) % mod self . p [ i ] = ( self . p [ i - 1 ] * base ) % mod def query ( self , l : int , r : int ) -> int : return ( self . h [ r ] - self . h [ l - 1 ] * self . p [ r - l + 1 ]) % self . mod class Solution : def minValidStrings ( self , words : List [ str ], target : str ) -> int : def f ( i : int ) -> int : l , r = 0 , min ( n - i , m ) while l < r : mid = ( l + r + 1 ) >> 1 sub = hashing . query ( i + 1 , i + mid ) if sub in s [ mid ]: l = mid else : r = mid - 1 return l base , mod = 13331 , 998244353 hashing = Hashing ( target , base , mod ) m = max ( len ( w ) for w in words ) s = [ set () for _ in range ( m + 1 )] for w in words : h = 0 for j , c in enumerate ( w , 1 ): h = ( h * base + ord ( c )) % mod s [ j ]. add ( h ) ans = last = mx = 0 n = len ( target ) for i in range ( n ): dist = f ( i ) mx = max ( mx , i + dist ) if i == last : if i == mx : return - 1 last = mx ans += 1 return ans

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