# 1234. Replace the Substring for Balanced String

oYu are given a string containing only 4 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 the original string s balanced.

Return 0 if the string is already balanced.

Example 1:

Input: s = "QWER"
Output: 0
Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER". 

Example 4:

Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

# Solution

Approach 1: sliding window.

Approach 2: ...

# Code (Python)

Approach 1:

import collections
class Solution:
    def balancedString(self, s: str) -> int:
        # get stats of overflowing chars and surplus, then use sliding window to find shortest substring
        counts = collections.Counter(s)
        surplus = {}
        for letter in ['Q', 'W', 'E', 'R']:
            if counts[letter] > len(s) / 4:
                surplus[letter] = counts[letter] - len(s) / 4
        if not surplus:
            return 0
        
        shortest_len = len(s)
        left = 0
        for right in range(len(s)):
            if s[right] in surplus:
                surplus[s[right]] -= 1
                if any([val > 0 for val in surplus.values()]):
                    continue
                while left < right and (s[left] not in surplus or surplus[s[left]] + 1 <= 0):
                    if s[left] in surplus and surplus[s[left]] + 1 <= 0:
                        surplus[s[left]] += 1
                    left += 1
                shortest_len = min(shortest_len, right - left + 1)
        
        return shortest_len

Approach 2:

# Code (C++)

Approach 1:

Approach 2: