Replace the Substring for Balanced String [Medium] — Two Ptr

Problem Statement

String s contains only Q,W,E,R. A balanced string has n/4 of each. You can replace any substring. Return minimum length of that substring.

Input: s="QWER" → Output: 0 (already balanced)
Input: s="QQWE" → Output: 1 (replace first Q with R)

Intuition

Characters outside the window must have count <= n/4 each (the excess must be in the window to replace). Shrink window from left while condition holds.

Solutions

C++

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

Python

from collections import Counter

def balancedString(s: str) -> int:
    n = len(s)
    k = n // 4
    cnt = Counter(s)
    if all(cnt[c] == k for c in 'QWER'):
        return 0
    left = ans = n
    for right, c in enumerate(s):
        cnt[c] -= 1
        while left <= right and all(cnt[c] <= k for c in 'QWER'):
            ans = min(ans, right - left + 1)
            cnt[s[left]] += 1
            left += 1
    return ans

Complexity

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