Replace the Substring for Balanced String

medium sliding window two pointers string

Problem

You are given a string s of length n containing only the characters 'Q', 'W', 'E', and 'R'. The string is balanced if each of the four characters appears exactly n/4 times. You may replace one contiguous substring with any other string of the same length. Return the minimum length of the substring you must replace to make s balanced. Return 0 if it is already balanced.

Inputs = "QWWE"

Output1

n = 4, so each letter must appear once. Replacing the substring "W" at index 2 with "R" gives "QWRE", which is balanced.

s (letters Q W E R only)

def balanced_string(s):
    n = len(s)
    k = n // 4
    count = {c: 0 for c in "QWER"}
    for c in s:
        count[c] += 1
    if all(count[c] == k for c in "QWER"):
        return 0
    best = n
    left = 0
    for right in range(n):
        count[s[right]] -= 1
        while left < n and all(count[c] <= k for c in "QWER"):
            best = min(best, right - left + 1)
            count[s[left]] += 1
            left += 1
    return best

function balancedString(s) {
  const n = s.length, k = n / 4;
  const count = { Q: 0, W: 0, E: 0, R: 0 };
  for (const c of s) count[c]++;
  const ok = () => "QWER".split("").every(c => count[c] <= k);
  if ("QWER".split("").every(c => count[c] === k)) return 0;
  let best = n, left = 0;
  for (let right = 0; right < n; right++) {
    count[s[right]]--;
    while (left < n && ok()) {
      best = Math.min(best, right - left + 1);
      count[s[left]]++;
      left++;
    }
  }
  return best;
}

class Solution {
    public int balancedString(String s) {
        int n = s.length(), k = n / 4;
        int[] count = new int[128];
        for (char c : s.toCharArray()) count[c]++;
        if (ok(count, k)) return 0;
        int best = n, left = 0;
        for (int right = 0; right < n; right++) {
            count[s.charAt(right)]--;
            while (left < n && ok(count, k)) {
                best = Math.min(best, right - left + 1);
                count[s.charAt(left)]++;
                left++;
            }
        }
        return best;
    }
    private boolean ok(int[] c, int k) {
        return c['Q'] <= k && c['W'] <= k && c['E'] <= k && c['R'] <= k;
    }
}

int balancedString(string s) {
    int n = s.size(), k = n / 4;
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    auto ok = [&]() {
        return count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k;
    };
    if (count['Q'] == k && count['W'] == k && count['E'] == k && count['R'] == k) return 0;
    int best = n, left = 0;
    for (int right = 0; right < n; right++) {
        count[s[right]]--;
        while (left < n && ok()) {
            best = min(best, right - left + 1);
            count[s[left]]++;
            left++;
        }
    }
    return best;
}

Explanation

We must replace one contiguous chunk so each of Q, W, E, R appears exactly n/4 times. The neat reframing: whatever chunk we replace, we can fill it with anything, so a chunk works as long as the letters outside it are not already over the limit k = n/4.

So the task becomes: find the shortest window such that, after removing it, every letter's count is at most k. We hunt for that with a sliding window over the counts.

We start with the full counts of the whole string. As right moves forward, we subtract s[right] from count (pretending that character is inside the replaceable window). Whenever every letter outside is at most k (the ok check), the current window is replaceable, so we record its length and shrink from the left by adding s[left] back.

The smallest valid window length we ever see is the answer. If the string is already balanced from the start, we return 0 right away.

Example: s = "QWWE", n = 4, k = 1. There is an extra W. The shortest replaceable window is the single W at index 2 — swapping it for R gives "QWRE" — so the answer is 1.

Time: O(n) Space: O(1)