Replace the substring for balanced string

String Sliding Window

40.6% acceptance

Feb 25, 2026

1284

224

You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'. A string is said to be balanced if each of its characters appears n / 4 times where n is the length of the string. Return the minimum length of the substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn balanced_string(s: String) -> i32 {
    let n = s.len() as i32;
    let target = n / 4;
    let s: Vec<u8> = s.bytes().collect();
    let mut cnt = [0i32; 4]; // Q=0, W=1, E=2, R=3
    let idx = |c: u8| match c { b'Q' => 0, b'W' => 1, b'E' => 2, _ => 3 };

    for &c in &s {
      cnt[idx(c)] += 1;
    }

    // Already balanced
    if cnt.iter().all(|&x| x == target) {
      return 0;
    }

    let mut ans = n;
    let mut left = 0usize;

    for right in 0..s.len() {
      let rc = idx(s[right]);
      cnt[rc] -= 1;

      // Shrink window while all outside-counts are <= target
      while left <= right && cnt.iter().all(|&x| x <= target) {
        ans = ans.min((right - left + 1) as i32);
        let lc = idx(s[left]);
        cnt[lc] += 1;
        left += 1;
      }
    }
    ans
  }
}