Count substrings that can be rearranged to contain a string i

Hash Table String Sliding Window

42.7% acceptance

Feb 25, 2026

123

You are given two strings word1 and word2. A string x is called valid if x can be rearranged to have word2 as a prefix. Return the total number of valid substrings of word1.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn valid_substring_count(word1: String, word2: String) -> i64 {
    // A substring word1[l..=r] is valid if for each char c: count(c in word1[l..r]) >= count(c in word2)
    // Sliding window: for each r, find smallest l such that window is valid
    // "need[c]" = count of c in word2. Track "deficit" = number of chars with count < needed.
    let w1 = word1.as_bytes();
    let w2 = word2.as_bytes();
    let n = w1.len();
    
    let mut need = [0i32; 26];
    for &c in w2 {
      need[(c - b'a') as usize] += 1;
    }
    
    let mut window = [0i32; 26];
    let mut deficit = need.iter().filter(|&&x| x > 0).count() as i32;
    let mut left = 0usize;
    let mut ans = 0i64;
    
    for right in 0..n {
      let c = (w1[right] - b'a') as usize;
      window[c] += 1;
      if need[c] > 0 && window[c] == need[c] {
        deficit -= 1;
      }
      // Shrink from left while valid
      while deficit == 0 {
        // All substrings from left to right..n-1 are valid
        ans += (n - right) as i64;
        let lc = (w1[left] - b'a') as usize;
        window[lc] -= 1;
        if need[lc] > 0 && window[lc] < need[lc] {
          deficit += 1;
        }
        left += 1;
      }
    }
    ans
  }
}