LeetCode #3292 — HARD

Minimum Number of Valid Strings to Form Target II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Dynamic Programming · Segment Tree · String Matching

Example 1

["abc","aaaaa","bcdef"]
"aabcdabc"

Example 2

["abababab","ab"]
"ababaababa"

Example 3

["abcdef"]
"xyz"

Core Insight

What unlocks the optimal approach

Let <code>dp[i]</code> be the minimum cost to form the prefix of length <code>i</code> of <code>target</code>.
Use Rabin-Karp to hash every prefix and store it in a HashSet.
Use Binary search to find the longest substring starting at index <code>i</code> (<code>target[i..j]</code>) that has a hash present in the HashSet.
Inverse Modulo precomputation can optimise hash calculation.
Use Lazy Segment Tree, or basic Segment Tree to update <code>dp[i..j]</code>.
Is it possible to use two TreeSets to update <code>dp[i..j]</code>?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3292: Minimum Number of Valid Strings to Form Target II
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;
    }
}

// Accepted solution for LeetCode #3292: Minimum Number of Valid Strings to Form Target II
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
}

# Accepted solution for LeetCode #3292: Minimum Number of Valid Strings to Form Target II
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

// Accepted solution for LeetCode #3292: Minimum Number of Valid Strings to Form Target II
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
    }
}

// Accepted solution for LeetCode #3292: Minimum Number of Valid Strings to Form Target II
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;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × log n + L)

Space

O(n + L)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.