Skip to main content
Back to problems
#3292
Hard Algorithms

Minimum number of valid strings to form target ii

Array String Binary Search Dynamic Programming Segment Tree Rolling Hash String Matching Hash Function
20.4% acceptance
Feb 25, 2026
85
10
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. Note: memory limits are smaller than usual, so you must implement a solution with linear runtime complexity.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
    let t = target.as_bytes();
    let n = t.len();

    // For each position i in target, compute max_match[i]:
    // the longest prefix of any word that matches t[i..].
    // Use Z-function on (word + '#' + target) for each word.
    let mut max_match = vec![0usize; n];

    for w in &words {
      let wb = w.as_bytes();
      let wl = wb.len();
      // Build concatenated string: word + '#' + target
      let mut s: Vec<u8> = Vec::with_capacity(wl + 1 + n);
      s.extend_from_slice(wb);
      s.push(b'#');
      s.extend_from_slice(t);
      let z = Self::z_function(&s);
      // z[wl + 1 + i] = length of longest prefix of s that matches s[wl+1+i..]
      // = length of longest prefix of word that matches t[i..], capped at wl
      for i in 0..n {
        let zi = z[wl + 1 + i].min(wl);
        if zi > max_match[i] {
          max_match[i] = zi;
        }
      }
    }

    // Greedy jump cover (Jump Game II style):
    // curr_reach: rightmost position covered with `ans` valid strings
    // far: rightmost position coverable by taking one more step
    let mut ans = 0i32;
    let mut curr_reach = 0usize;
    let mut far = 0usize;
    for i in 0..n {
      if i > curr_reach {
        return -1; // gap: cannot reach position i
      }
      far = far.max(i + max_match[i]);
      if i == curr_reach {
        if far <= curr_reach {
          return -1; // cannot extend
        }
        curr_reach = far;
        ans += 1;
        if curr_reach >= n {
          break;
        }
      }
    }
    if curr_reach >= n { ans } else { -1 }
  }

  fn z_function(s: &[u8]) -> Vec<usize> {
    let n = s.len();
    let mut z = vec![0usize; n];
    z[0] = n;
    let (mut l, mut r) = (0usize, 0usize);
    for i in 1..n {
      if i < r {
        z[i] = (r - i).min(z[i - l]);
      }
      while i + z[i] < n && s[z[i]] == s[i + z[i]] {
        z[i] += 1;
      }
      if i + z[i] > r {
        l = i;
        r = i + z[i];
      }
    }
    z
  }
}