Code Implementation

class Solution:
    def balancedString(self, s: str) -> int:
        from collections import Counter
        n = len(s)
        required = n // 4
        count = Counter(s)
        if all(count[c] == required for c in 'QWER'):
            return 0

        min_len = n
        left = 0
        for right in range(n):
            count[s[right]] -= 1
            while left < n and all(count[c] <= required for c in 'QWER'):
                min_len = min(min_len, right - left + 1)
                count[s[left]] += 1
                left += 1
        return min_len
      

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

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

var balancedString = function(s) {
    const n = s.length, required = n / 4;
    const count = {'Q':0,'W':0,'E':0,'R':0};
    for (let c of s) count[c]++;
    if (count['Q'] === required && count['W'] === required && count['E'] === required && count['R'] === required)
        return 0;
    let minLen = n, left = 0;
    for (let right = 0; right < n; right++) {
        count[s[right]]--;
        while (left < n && count['Q'] <= required && count['W'] <= required && count['E'] <= required && count['R'] <= required) {
            minLen = Math.min(minLen, right - left + 1);
            count[s[left]]++;
            left++;
        }
    }
    return minLen;
};
      

Problem Description

Given a string s of length n, where n is divisible by 4, and s consists only of the characters 'Q', 'W', 'E', and 'R', you are to replace a substring of s with another string of the same length (the replacement can be any string) so that the resulting string is balanced. A string is balanced if each of the four characters appears exactly n/4 times.

Your task is to return the length of the smallest substring that can be replaced to make s balanced.

• There is always at least one valid solution.
• You may not reuse elements: the substring to replace must be contiguous.
• Only one substring can be replaced.

Thought Process

To solve this problem, first notice that the only way for the string to be unbalanced is if some characters appear more than n/4 times. The extra occurrences must be "removed" by replacing a substring containing enough of these surplus characters. The goal is to find the shortest substring whose replacement will balance the string.

A brute-force attempt would be to check every possible substring, replace it, and check if the result is balanced. But this is inefficient, especially for large strings.

Instead, we can optimize by focusing on the minimum window containing all the excess characters. If we can "cover" all the surplus by removing a window, the rest of the string will have at most n/4 of each character.

This naturally leads to the sliding window technique, where we expand and contract a window to find the minimal length that satisfies our condition.

Solution Approach

• Step 1: Count Characters
  Count how many times each of 'Q', 'W', 'E', 'R' appears in s. The required count for each is n/4.
• Step 2: Identify Surplus
  For each character, if its count is greater than n/4, note the surplus. Only these surplus characters need to be "removed" via replacement.
• Step 3: Sliding Window
  Use two pointers (left and right) to define a window. As you move right forward, decrement the count of the current character. When the remaining string (outside the window) has no surplus (i.e., all counts ≤ n/4), try to shrink the window from the left to find the minimal length.
• Step 4: Track Minimum
  Each time the condition is satisfied, update the minimal window length.
• Step 5: Return Result
  After scanning the string, return the smallest window length found.

We use a hash map (or array) for character counts because lookups and updates are O(1).

Example Walkthrough

Example Input: s = "QWERQQQQ"

• Length n = 8, so required per char is 2.
• Counts: Q=5, W=1, E=1, R=1
• Surplus: Q has 3 extra, others are fine.
• Start sliding window:
  • Right pointer at 0: Remove Q (counts: Q=4), not enough removed.
  • Right at 1: Remove W (Q=4, W=0), still surplus Q.
  • Right at 2: Remove E (Q=4, E=0), still surplus Q.
  • Right at 3: Remove R (Q=4, R=0), still surplus Q.
  • Right at 4: Remove Q (Q=3), still surplus Q.
  • Right at 5: Remove Q (Q=2), now Q is at required! Now, try to shrink from left:
  • Move left to 1: Add back Q (Q=3), surplus again. Stop shrinking.
  • Window [0,5] length 6 is valid.
  • Continue: right at 6, remove Q (Q=1), now Q below required, but that's fine.
  • Shrink left: left at 1, add W (W=1), still valid; length 6.
  • left at 2, add E (E=1), still valid; length 5.
  • left at 3, add R (R=1), still valid; length 4.
  • left at 4, add Q (Q=2), still valid; length 3.
  • left at 5, add Q (Q=3), now Q surplus again, stop.
• The minimal window found is of length 3.

Time and Space Complexity

• Brute-force: Checking every substring is O(n²) time and O(1) space.
• Optimized (Sliding Window): Each character is considered at most twice (once by left, once by right), so total time is O(n). Space is O(1) since only a fixed-size count map is needed.

This efficiency comes from not re-scanning the whole string for every window, but updating counts incrementally.

Summary

The key insight is to notice that we only need to "remove" surplus characters, and that replacing a substring covering all surplus is sufficient. The sliding window approach efficiently finds the minimal such substring, resulting in an elegant O(n) solution. This problem demonstrates how recognizing the right substructure (the window containing all surplus) can turn a brute-force search into a fast, practical algorithm.