Minimum Number of Valid Strings to Form Target II solution and explanation
The 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 <= 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.
def min_valid_strings_to_form_target(words, target):
n = len(target)
dp = [float('inf')] * (n + 1)
dp[0] = 0
words_set = set(words)
for i in range(1, n + 1):
for j in range(i):
if target[j:i] in words_set:
dp[i] = min(dp[i], dp[j] + 1)
return -1 if dp[n] == float('inf') else dp[n]#include <string>
#include <vector>
#include <unordered_set>
int minValidStringsToFormTarget(std::vector<std::string>& words, std::string target) {
int n = target.size();
std::vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
std::unordered_set<std::string> wordsSet(words.begin(), words.end());
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (wordsSet.count(target.substr(j, i - j))) {
dp[i] = std::min(dp[i], dp[j] + 1);
}
}
}
return dp[n] == INT_MAX ? -1 : dp[n];
}function minValidStringsToFormTarget(words, target) {
const n = target.length;
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
const wordsSet = new Set(words);
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (wordsSet.has(target.substring(j, i))) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n] === Infinity ? -1 : dp[n];
}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.
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.
def min_valid_strings_backtrack(words, target):
def backtrack(index, count):
if index == len(target):
return count
min_count = float('inf')
for word in words:
if target.startswith(word, index):
result = backtrack(index + len(word), count + 1)
min_count = min(min_count, result)
return min_count
result = backtrack(0, 0)
return -1 if result == float('inf') else resultfunction minValidStringsBacktrack(words, target) {
function backtrack(index, count) {
if (index === target.length) return count;
let minCount = Infinity;
for (const word of words) {
if (target.startsWith(word, index)) {
const result = backtrack(index + word.length, count + 1);
minCount = Math.min(minCount, result);
}
}
return minCount;
}
const result = backtrack(0, 0);
return result === Infinity ? -1 : result;
}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.
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.
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;
}
}function minValidStrings(words: string[], target: string): number {
class Hashing {
private p: bigint[];
private h: bigint[];
private mod: bigint;
constructor(word: string, base: bigint, mod: bigint) {
const n = word.length;
this.p = new Array<bigint>(n + 1).fill(0n);
this.h = new Array<bigint>(n + 1).fill(0n);
this.mod = mod;
this.p[0] = 1n;
for (let i = 1; i <= n; ++i) {
this.p[i] = (this.p[i - 1] * base) % mod;
this.h[i] = (this.h[i - 1] * base + BigInt(word.charCodeAt(i - 1))) % mod;
}
}
query(l: number, r: number): bigint {
const res =
(this.h[r] - ((this.h[l - 1] * this.p[r - l + 1]) % this.mod) + this.mod) %
this.mod;
return res;
}
}
const base = 13331n;
const mod = 998244353n;
const hashing = new Hashing(target, base, mod);
const m = Math.max(0, ...words.map(w => w.length));
const s: Set<bigint>[] = Array.from({ length: m + 1 }, () => new Set<bigint>());
for (const w of words) {
let h = 0n;
for (let j = 0; j < w.length; ++j) {
h = (h * base + BigInt(w.charCodeAt(j))) % mod;
s[j + 1].add(h);
}
}
const n = target.length;
let ans = 0;
let last = 0;
let mx = 0;
const f = (i: number): number => {
let l = 0;
let r = Math.min(n - i, m);
while (l < r) {
const mid = (l + r + 1) >> 1;
const sub = hashing.query(i + 1, i + mid);
if (s[mid].has(sub)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
};
for (let i = 0; i < n; ++i) {
const dist = f(i);
mx = Math.max(mx, i + dist);
if (i === last) {
if (i === mx) {
return -1;
}
last = mx;
ans++;
}
}
return ans;
}type Hashing struct {
p []int64
h []int64
mod int64
}
func NewHashing(word string, base int64, mod int64) *Hashing {
n := len(word)
p := make([]int64, n+1)
h := make([]int64, n+1)
p[0] = 1
for i := 1; i <= n; i++ {
p[i] = (p[i-1] * base) % mod
h[i] = (h[i-1]*base + int64(word[i-1])) % mod
}
return &Hashing{p, h, mod}
}
func (hashing *Hashing) Query(l, r int) int64 {
return (hashing.h[r] - hashing.h[l-1]*hashing.p[r-l+1]%hashing.mod + hashing.mod) % hashing.mod
}
func minValidStrings(words []string, target string) (ans int) {
base, mod := int64(13331), int64(998244353)
hashing := NewHashing(target, base, mod)
m, n := 0, len(target)
for _, w := range words {
m = max(m, len(w))
}
s := make([]map[int64]bool, m+1)
f := func(i int) int {
l, r := 0, int(math.Min(float64(n-i), float64(m)))
for l < r {
mid := (l + r + 1) >> 1
sub := hashing.Query(i+1, i+mid)
if s[mid][sub] {
l = mid
} else {
r = mid - 1
}
}
return l
}
for _, w := range words {
h := int64(0)
for j := 0; j < len(w); j++ {
h = (h*base + int64(w[j])) % mod
if s[j+1] == nil {
s[j+1] = make(map[int64]bool)
}
s[j+1][h] = true
}
}
var last, mx int
for i := 0; i < n; i++ {
dist := f(i)
mx = max(mx, i+dist)
if i == last {
if i == mx {
return -1
}
last = mx
ans++
}
}
return ans
}use std::collections::HashSet;
use std::cmp::max;
struct Hashing {
p: Vec<i64>,
h: Vec<i64>,
base: i64,
modv: i64,
}
impl Hashing {
fn new(word: &str, base: i64, modv: i64) -> Self {
let n = word.len();
let mut p = vec![0; n + 1];
let mut h = vec![0; n + 1];
let bytes = word.as_bytes();
p[0] = 1;
for i in 1..=n {
p[i] = p[i - 1] * base % modv;
h[i] = (h[i - 1] * base + bytes[i - 1] as i64) % modv;
}
Self { p, h, base, modv }
}
fn query(&self, l: usize, r: usize) -> i64 {
let mut res = self.h[r] - self.h[l - 1] * self.p[r - l + 1] % self.modv;
if res < 0 {
res += self.modv;
}
res % self.modv
}
}
impl Solution {
pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
let base = 13331;
let modv = 998_244_353;
let hashing = Hashing::new(&target, base, modv);
let m = words.iter().map(|w| w.len()).max().unwrap_or(0);
let mut s: Vec<HashSet<i64>> = vec![HashSet::new(); m + 1];
for w in &words {
let mut h = 0i64;
for (j, &b) in w.as_bytes().iter().enumerate() {
h = (h * base + b as i64) % modv;
s[j + 1].insert(h);
}
}
let n = target.len();
let bytes = target.as_bytes();
let mut ans = 0;
let mut last = 0;
let mut mx = 0;
let f = |i: usize, n: usize, m: usize, s: &Vec<HashSet<i64>>, hashing: &Hashing| -> usize {
let mut l = 0;
let mut r = std::cmp::min(n - i, m);
while l < r {
let mid = (l + r + 1) >> 1;
let sub = hashing.query(i + 1, i + mid);
if s[mid].contains(&sub) {
l = mid;
} else {
r = mid - 1;
}
}
l
};
for i in 0..n {
let dist = f(i, n, m, &s, &hashing);
mx = max(mx, i + dist);
if i == last {
if i == mx {
return -1;
}
last = mx;
ans += 1;
}
}
ans
}
}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 | – |
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 |
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 is classified as a Hard problem. It combines multiple advanced concepts including dynamic programming, rolling hash, substring matching, and optimization of segmentation problems under strict constraints.
Minimum Number of Valid Strings to Form Target II Python/Java solution
Python, JavaScript, and C++ implementations typically use dynamic programming with rolling hash for substring validation. Each step updates dp based on matching valid string lengths. The approach keeps substring checks O(1) and ensures the minimum number of segments is computed efficiently.
How to solve Minimum Number of Valid Strings to Form Target II in O(n log n)?
Compute prefix hashes for the target string and store hashes of valid strings grouped by length. Use dynamic programming where dp[i] represents the minimum segments needed to reach position i. For each index, check candidate lengths using hash comparison and update dp transitions. Binary search over candidate lengths keeps the number of checks small.
What is the best approach for Minimum Number of Valid Strings to Form Target II?
The most efficient approach uses dynamic programming combined with rolling hash or fast substring matching. Define dp[i] as the minimum number of strings needed to form the prefix ending at index i. Rolling hash allows constant-time substring comparisons, reducing overall complexity to about O(n log n) depending on implementation.
Is Minimum Number of Valid Strings to Form Target II asked at Google/Amazon/Meta?
Problems involving string segmentation, rolling hash, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of substring matching optimization and DP state transitions.
What data structure is used in Minimum Number of Valid Strings to Form Target II?
The main structures include a dynamic programming array, hash tables for storing precomputed string hashes, and sometimes prefix hash arrays for the target string. Some implementations also use segment trees or binary search structures to accelerate substring matching.
What is the time complexity of Minimum Number of Valid Strings to Form Target II?
The optimized dynamic programming solution runs in roughly O(n log n) time with O(n) space when rolling hash and efficient substring lookups are used. Simpler recursive or greedy approaches with backtracking may degrade to O(n^2) in worst cases due to repeated substring checks.