Find all good strings

String Dynamic Programming String Matching

45.1% acceptance

Feb 25, 2026

531

130

Given the strings s1 and s2 of size n and the string evil, return the number of good strings. A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 109 + 7.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_good_strings(n: i32, s1: String, s2: String, evil: String) -> i32 {
    const MOD: u64 = 1_000_000_007;
    let n = n as usize;
    let s1 = s1.as_bytes();
    let s2 = s2.as_bytes();
    let evil = evil.as_bytes();
    let m = evil.len();
    // KMP failure function for evil
    let mut fail = vec![0usize; m];
    let mut k = 0usize;
    for i in 1..m {
      while k > 0 && evil[k] != evil[i] { k = fail[k - 1]; }
      if evil[k] == evil[i] { k += 1; }
      fail[i] = k;
    }
    // KMP transition
    let kmp_next = |state: usize, c: u8| -> usize {
      let mut s = state;
      while s > 0 && evil[s] != c { s = fail[s - 1]; }
      if evil[s] == c { s + 1 } else { 0 }
    };
    // Count strings of length n: not containing evil, >= s1 if tight_lo, <= s2 if tight_hi
    // dp[tight_lo][tight_hi][evil_state] = count
    // Use iterative DP over positions
    // State: (tight_lo: bool, tight_hi: bool, evil_state: usize)
    // Use HashMap or 3D array
    let _states = 2 * 2 * m; // 4 * m states
    let idx = |tl: usize, th: usize, es: usize| tl * 2 * m + th * m + es;
    let mut dp = vec![0u64; 4 * m];
    dp[idx(1, 1, 0)] = 1;
    for i in 0..n {
      let mut ndp = vec![0u64; 4 * m];
      for tl in 0..2usize {
        for th in 0..2usize {
          for es in 0..m {
            let cnt = dp[idx(tl, th, es)];
            if cnt == 0 { continue; }
            let lo = if tl == 1 { s1[i] } else { b'a' };
            let hi = if th == 1 { s2[i] } else { b'z' };
            for c in lo..=hi {
              let nes = kmp_next(es, c);
              if nes == m { continue; } // evil substring found
              let ntl = if tl == 1 && c == lo { 1 } else { 0 };
              let nth = if th == 1 && c == hi { 1 } else { 0 };
              ndp[idx(ntl, nth, nes)] = (ndp[idx(ntl, nth, nes)] + cnt) % MOD;
            }
          }
        }
      }
      dp = ndp;
    }
    let mut ans = 0u64;
    for tl in 0..2usize {
      for th in 0..2usize {
        for es in 0..m {
          ans = (ans + dp[idx(tl, th, es)]) % MOD;
        }
      }
    }
    ans as i32
  }
}