Count substrings that can be rearranged to contain a string ii

Hash Table String Sliding Window

56.1% acceptance

Feb 25, 2026

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. Note: memory limits are smaller than usual, so you must implement a solution with linear runtime complexity.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn valid_substring_count(word1: String, word2: String) -> i64 {
    // Same sliding window O(n) approach as version I
    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;
      }
      while deficit == 0 {
        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
  }
}