Replace the Substring for Balanced String

Problem

Examples

Solution

Method 1 – Sliding Window with Frequency Count

Intuition

To balance the string, we need each character ('Q', 'W', 'E', 'R') to appear exactly n/4 times. The problem reduces to finding the smallest substring that, if replaced, would make the string balanced. We can use a sliding window to find the minimum window that covers all excess characters.

Approach

1. Count the frequency of each character in the string.
2. Set the target count for each character as n/4.
3. Use a sliding window (two pointers) to find the smallest window such that, if we replace it, the remaining string has no character exceeding the target count.
4. Move the right pointer to expand the window and the left pointer to shrink it while the condition is satisfied.
5. Track the minimum window length found.

Code

Java

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

Python

class Solution:
    def balancedString(self, s: str) -> int:
        from collections import Counter
        n = len(s)
        cnt = Counter(s)
        ans = n
        left = 0
        for right in range(n):
            cnt[s[right]] -= 1
            while left < n and all(cnt[c] <= n // 4 for c in 'QWER'):
                ans = min(ans, right - left + 1)
                cnt[s[left]] += 1
                left += 1
        return ans

C++

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

Go

func balancedString(s string) int {
    n := len(s)
    cnt := make([]int, 128)
    for i := 0; i < n; i++ {
        cnt[s[i]]++
    }
    ans, left := n, 0
    for right := 0; right < n; right++ {
        cnt[s[right]]--
        for left < n && cnt['Q'] <= n/4 && cnt['W'] <= n/4 && cnt['E'] <= n/4 && cnt['R'] <= n/4 {
            if ans > right-left+1 {
                ans = right - left + 1
            }
            cnt[s[left]]++
            left++
        }
    }
    return ans
}

Kotlin

class Solution {
    fun balancedString(s: String): Int {
        val n = s.length
        val cnt = IntArray(128)
        for (c in s) cnt[c.code]++
        var ans = n
        var left = 0
        for (right in 0 until n) {
            cnt[s[right].code]--
            while (left < n && cnt['Q'.code] <= n/4 && cnt['W'.code] <= n/4 && cnt['E'.code] <= n/4 && cnt['R'.code] <= n/4) {
                ans = minOf(ans, right - left + 1)
                cnt[s[left].code]++
                left++
            }
        }
        return ans
    }
}

Rust

impl Solution {
    pub fn balanced_string(s: String) -> i32 {
        let n = s.len();
        let mut cnt = vec![0; 128];
        for &b in s.as_bytes() {
            cnt[b as usize] += 1;
        }
        let (mut ans, mut left) = (n, 0);
        let s_bytes = s.as_bytes();
        for right in 0..n {
            cnt[s_bytes[right] as usize] -= 1;
            while left < n && cnt['Q' as usize] <= n/4 && cnt['W' as usize] <= n/4 && cnt['E' as usize] <= n/4 && cnt['R' as usize] <= n/4 {
                ans = ans.min(right - left + 1);
                cnt[s_bytes[left] as usize] += 1;
                left += 1;
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    balancedString(s: string): number {
        const n = s.length;
        const cnt = Array(128).fill(0);
        for (const c of s) cnt[c.charCodeAt(0)]++;
        let ans = n, left = 0;
        for (let right = 0; right < n; right++) {
            cnt[s.charCodeAt(right)]--;
            while (left < n && cnt['Q'.charCodeAt(0)] <= n/4 && cnt['W'.charCodeAt(0)] <= n/4 && cnt['E'.charCodeAt(0)] <= n/4 && cnt['R'.charCodeAt(0)] <= n/4) {
                ans = Math.min(ans, right - left + 1);
                cnt[s.charCodeAt(left)]++;
                left++;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of the string, since each character is visited at most twice.
• 🧺 Space complexity: O(1), since the character set is fixed and small.