Maximum difference between even and odd frequency ii

String Sliding Window Enumeration Prefix Sum

48.7% acceptance

Feb 25, 2026

392

105

You are given a string s and an integer k. Your task is to find the maximum difference between the frequency of two characters, freq[a] - freq[b], in a substring subs of s, such that: subs has a size of at least k. Character a has an odd frequency in subs. Character b has a non-zero even frequency in subs. Return the maximum difference. Note that subs can contain more than 2 distinct characters.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_difference(s: String, k: i32) -> i32 {
    let n = s.len();
    let k = k as usize;
    let inf = i32::MAX / 2;
    let mut ans = i32::MIN / 2;

    // Build prefix counts for all 5 digits in a single O(n) pass,
    // avoiding 40 separate array passes (2 per pair × 20 pairs).
    let mut prefix = vec![[0i32; 5]; n + 1];
    for (i, b) in s.bytes().enumerate() {
      prefix[i + 1] = prefix[i];
      prefix[i + 1][(b - b'0') as usize] += 1;
    }
    let total = prefix[n];

    // best_safe[pa_parity][pb_parity] = min(pa[l]-pb[l]) over promoted l's.
    // A candidate l is "promoted" once prefix_b[r] >= prefix_b[l] + 2.
    // prefix_b is non-decreasing, so promotion uses a monotone pointer — O(n) total.
    let mut queue: Vec<usize> = Vec::with_capacity(n + 1);

    for a in 0..5usize {
      if total[a] == 0 { continue; }            // a never appears → cnt_a always 0 (even), skip
      for b in 0..5usize {
        if a == b { continue; }
        if total[b] < 2 { continue; }          // b can't reach even freq ≥ 2, skip

        let mut best_safe = [[inf; 2]; 2];
        queue.clear();
        let mut ptr = 0usize;

        for r in k..=n {
          // Enqueue the new candidate l = r - k
          queue.push(r - k);

          // Promote all queued l's satisfying prefix_b[l] + 2 <= prefix_b[r]
          let pb_r_val = prefix[r][b];
          while ptr < queue.len() && prefix[queue[ptr]][b] + 2 <= pb_r_val {
            let ll = queue[ptr];
            ptr += 1;
            let ppa = (prefix[ll][a] % 2) as usize;
            let ppb = (prefix[ll][b] % 2) as usize;
            let vv = prefix[ll][a] - prefix[ll][b];
            if vv < best_safe[ppa][ppb] { best_safe[ppa][ppb] = vv; }
          }

          // Query: want pa_parity flipped, same pb_parity
          let pa_r = (prefix[r][a] % 2) as usize;
          let pb_r = (prefix[r][b] % 2) as usize;
          let bv = best_safe[1 - pa_r][pb_r];
          if bv != inf {
            let diff = (prefix[r][a] - prefix[r][b]) - bv;
            if diff > ans { ans = diff; }
          }
        }
      }
    }
    ans
  }
}