# Minimum Number of Valid Strings to Form Target II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-valid-strings-to-form-target-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String, Segment Tree
---
## Problem
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 * 104`
* The input is generated such that `sum(words[i].length) <= 105`.
* `words[i]` consists only of lowercase English letters.
* `1 <= target.length <= 5 * 104`
* `target` consists only of lowercase English letters.

# Approaches
## Dynamic Programming with Naive Prefix Checking
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`.
**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.
**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.
### Explanation
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.

```java
public int minStrings(String[] words, String target) {
    int n = target.length();
    int[] dp = new int[n + 1];
    java.util.Arrays.fill(dp, n + 1);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] > n) {
                continue;
            }
            String sub = target.substring(j, i);
            boolean is_valid = false;
            for (String word : words) {
                if (word.startsWith(sub)) {
                    is_valid = true;
                    break;
                }
            }

            if (is_valid) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }

    return dp[n] > n ? -1 : dp[n];
}
```
### Algorithm
1. Let `n` be the length of the `target` string.
2. 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]`.
3. Initialize `dp[0] = 0` (an empty prefix requires 0 strings) and all other `dp[i]` to a value representing infinity (e.g., `n + 1`).
4. 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)`.
5. After the loops complete, if `dp[n]` is still infinity, it's impossible to form the `target`. Return -1.
6. Otherwise, `dp[n]` holds the minimum number of strings, so return `dp[n]`.

## Dynamic Programming with Trie
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.
**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.
**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.
### Explanation
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.

```java
class TrieNode {
    TrieNode[] children = new TrieNode[26];
}

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
    }
}

public int minStrings(String[] words, String target) {
    Trie trie = new Trie();
    int maxWordLength = 0;
    for (String word : words) {
        trie.insert(word);
        maxWordLength = Math.max(maxWordLength, word.length());
    }

    int n = target.length();
    int[] dp = new int[n + 1];
    java.util.Arrays.fill(dp, n + 1);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        if (dp[i] > n) {
            continue;
        }

        TrieNode curr = trie.root;
        // The inner loop will naturally break after at most maxWordLength iterations
        // because any valid prefix cannot be longer than the longest word.
        for (int j = i; j < n; j++) {
            int index = target.charAt(j) - 'a';
            if (curr.children[index] == null) {
                break;
            }
            curr = curr.children[index];
            // target.substring(i, j + 1) is a valid prefix
            dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);
        }
    }

    return dp[n] > n ? -1 : dp[n];
}
```
### Algorithm
1. **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.
2. **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`).
3. **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)`.
4. **Result**: After the loops, if `dp[n]` is infinity, return -1. Otherwise, return `dp[n]`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```