You 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".

 
Constraints:

1 <= s.length <= 10^5
s.length is a multiple of 4
s contains only 'Q', 'W', 'E' and 'R'.

Difficulty: interview

Starter code:

class Solution:
    def balancedString(self, s: str) -> int:
        

Solutions:
class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, lb, n_cnt = len(s), 0, collections.Counter(s)

        i = 0
        while i < len(s): 
            n_cnt[s[i]] -= 1     
            while lb < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(i - lb + 1))
                if ans == 0: return 0
                n_cnt[s[lb]] += 1
                lb += 1
                # here is actually a swap? 
            if lb > i: 
                i, lb = lb, i
            i +=1

        return ans
                
            
            
        
            
            


class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        
        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
                # here is actually a swap? 
            if p2 > p1: 
                p1, p2 = p2, p1
            p1 +=1

        return ans
                
            
            
        
            
            


class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
            if p2 > p1: 
                p1, p2 = p2, p1
            p1 +=1

        return ans
                
            
            
        
            
            


class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
            if p2 > p1: 
                p1, p2 = p2, p1
            p1 +=1
        return ans
    
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < min(p1+2, len(s)) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                # can go beyond one position
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
            # if p2 > p1: 
            #     p1, p2 = p2, p1
            p1 +=1
        return ans
                
            
            
        
            
            


class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
            if p2 > p1: 
                p1, p2 = p2, p1
            p1 +=1
        return ans
    
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, p1, p2, n_cnt = len(s), 0, 0, collections.Counter(s)

        while p1 < len(s): 
            n_cnt[s[p1]] -= 1     
            while p2 < min(p1+2, len(s)) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                ans = min(ans, abs(p1 - p2 + 1))
                n_cnt[s[p2]] += 1
                p2 += 1
            # if p2 > p1: 
            #     p1, p2 = p2, p1
            p1 +=1
        return ans
                
            
            
        
            
            


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

class Solution:
    def balancedString(self, s: str) -> int:
        # minimum window so that outside is possible
        if len(s) //4 != len(s) / 4: return -1 
        ans, lb, n_cnt = len(s), 0, collections.Counter(s)

        for i, l in enumerate(s): 
            n_cnt[l] -= 1               
            while lb < len(s) and all(len(s) / 4 >= n_cnt[c] for c in 'QWER'): 
                # how to shrink? 
                ans = min(ans, i - lb + 1)
                n_cnt[s[lb]] += 1
                lb += 1
                
        return ans