#3292

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Valid Strings to Form Target II

Compute the minimum number of valid strings from an array needed to construct a given target string efficiently using dynamic programming.

array string binary search dynamic programming segment tree

Problem Statement

Given an array of strings words and a string target, a string is considered valid if it matches a prefix of any string in words. You must compute how many valid strings must be concatenated to exactly form target.

Return the minimum number of valid strings needed. If no combination of valid strings can form target, return -1. Each string in words can be reused multiple times, and all strings contain only lowercase English letters.

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 * 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.

Solution Approach

Dynamic Programming Table

Define dp[i] as the minimum number of valid strings to form the prefix of target up to index i. Initialize dp[0] = 0 and all others to infinity. Iterate over target positions and update dp using all valid prefixes from words.

Prefix Lookup Optimization

Preprocess words into a trie or hashmap of prefixes for fast lookups. For each position in target, check all valid prefixes in O(1) to O(length of prefix) time, reducing redundant substring checks in DP updates.

Result Extraction

After filling dp, check dp[target.length]. If it remains infinity, return -1 indicating target formation is impossible. Otherwise, return dp[target.length] as the minimum concatenation count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N * L * W) where N is target length, L is maximum word length, and W is number of words, optimized with prefix hashing. Space complexity is O(N + total prefix storage) for DP and prefix structures.

What Interviewers Usually Probe

Mentions state transition dynamic programming and prefix concatenation strategy.
Asks about optimizing substring checks and reducing DP iteration overhead.
Explores edge cases where target cannot be formed or words are very long.

Common Pitfalls or Variants

Common pitfalls

Failing to consider all valid prefixes leads to incorrect DP updates.
Using naive substring comparisons results in TLE for large input sizes.
Returning wrong index offset or missing initial DP initialization at zero.

Follow-up variants

Limit reuse of words to at most once per concatenation, changing DP transitions.
Count all distinct ways to form target instead of minimum number.
Extend to allow words containing wildcards that match multiple characters.

FAQ

What is the core pattern behind Minimum Number of Valid Strings to Form Target II?

The core pattern is state transition dynamic programming, where dp[i] tracks the minimum concatenations needed for each target prefix.

Can words be reused multiple times in forming the target?

Yes, each word can be used multiple times, but the DP ensures only valid prefix concatenations are counted.

What if no combination of words can form the target?

The DP will leave dp[target.length] as infinity, and the algorithm returns -1 to indicate impossibility.

How does prefix preprocessing help in this problem?

Preprocessing into a trie or hashmap allows fast checking of valid prefixes, reducing redundant DP checks and improving efficiency.

Is there a space-efficient version for very long targets?

Yes, you can optimize space by storing only recent dp states or compressing the prefix structure, but time complexity depends on prefix checks.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

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

Continue Practicing

#3291 minimum number of valid strings to form target i #3529 count cells in overlapping horizontal and vertical substrings #3045 count prefix and suffix pairs ii