Length of the longest valid substring

Array Hash Table String Sliding Window

38.2% acceptance

Feb 25, 2026

614

You are given a string word and an array of strings forbidden. A string is called valid if none of its substrings are present in forbidden. Return the length of the longest valid substring of the string word. A substring is a contiguous sequence of characters in a string, possibly empty.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_valid_substring(word: String, forbidden: Vec<String>) -> i32 {
    use std::collections::HashSet;
    let forbidden_set: HashSet<&[u8]> = forbidden.iter().map(|s| s.as_bytes()).collect();
    let word = word.as_bytes();
    let n = word.len();
    let mut left = 0usize;
    let mut ans = 0usize;
    for right in 0..n {
      let lo = right.saturating_sub(9);
      for start in (lo..=right).rev() {
        if start < left { break; }
        if forbidden_set.contains(&word[start..=right]) {
          left = start + 1;
          break;
        }
      }
      ans = ans.max(right + 1 - left);
    }
    ans as i32
  }
}