You are given a string s of length n containing only four 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 s balanced. If s is already balanced, return 0.

&nbsp;
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". 


&nbsp;
Constraints:


	n == s.length
	4 &lt;= n &lt;= 105
	n is a multiple of 4.
	s contains only 'Q', 'W', 'E', and 'R'.


class Solution:
    def balancedString(self, s):
        count = collections.Counter(s)
        res = n = len(s)
        if all(n/4==count[char] for char in 'QWER'):
            return 0
        left = 0
        for right, char in enumerate(s):
            # replace char whose index==right to check if it is balanced
            count[char] -= 1
            # if it is balanced, window shrinks to get the smallest length of window
            while left <= right and all(n / 4 >= count[char] for char in 'QWER'):
                res = min(res, right - left + 1)
                count[s[left]] =count[s[left]]+ 1
                left += 1
        return res
class Solution {
    public int balancedString(String s) {
        int n = s.length(), ans = n, excess = 0;
        int[] cnt = new int[128];
        cnt['Q'] = cnt['W'] = cnt['E'] = cnt['R'] = -n/4;
        for (char ch : s.toCharArray()) if (++cnt[ch] == 1) excess++; //if count reaches 1, it is extra and to be removed.
        if (excess == 0) return 0;
        for (int i = 0, j = 0; i < n; i++){//i = window right end, j = window left end
            if (--cnt[s.charAt(i)] == 0) excess--; //remove letter at index i
            while (excess == 0){ //if no more excess, then 
                if (++cnt[s.charAt(j)] == 1) excess++; //we put letter at index j back
                ans = Math.min(i - j + 1, ans);; //and update ans accordingly
                j++;
            }
        }

        return ans;
    }
}
class Solution {
public:
    int balancedString(string s) {
      int n=s.length();
      unordered_map<char,int>umap;
      for(auto x:s)
      {
         umap[x]++;   
      }
        umap['Q']=umap['Q']-n/4>0?umap['Q']-n/4:0;
        umap['W']=umap['W']-n/4>0?umap['W']-n/4:0;
        umap['E']=umap['E']-n/4>0?umap['E']-n/4:0;
        umap['R']=umap['R']-n/4>0?umap['R']-n/4:0;
        int count=umap['Q']+umap['W']+umap['E']+umap['R'];
        if(count==0)
            return 0;
        int i=0,ans=INT_MAX;
        unordered_map<char,int>newMap;
        for(int j=0;j<n;j++)
        {
            newMap[s[j]]++;
            if(newMap[s[j]]<=umap[s[j]])
            {
                count--;
                while(count==0)
                {
                    newMap[s[i]]--;
                    if(newMap[s[i]]<umap[s[i]])
                    {
                        count++;
                        ans=min(ans,j-i+1);
                    }
                    i++;
                }
            }
        }
        return ans;
    }
};
var balancedString = function(s) {
    
    let output = Infinity;
    
    let map = {"Q":0, "W":0, "E":0, "R":0};
    
    for(let letter of s){
        map[letter]++;
    }
    
    let valueGoal = s.length / 4
        
    let remainder = 0;
    
    let count = 4;
    
    for(let [key, val] of Object.entries(map)){
        
        if(val > valueGoal){
            remainder = remainder + (val - valueGoal); 
        }
        
        if(val === valueGoal || val < valueGoal){
            map[key] = -Infinity;
            count--;
        }
    }
    
    if(remainder === 0){
        return 0;
    }
    
    let left = 0;
    
    let right = 0;
    
    while(right < s.length){

        if(map[s[right]] !== -Infinity){
            
            map[s[right]]--;

            if(map[s[right]] === valueGoal){
                count--;
            }
            
        }
        
        while(count === 0){

            output = Math.min(output, right - left + 1);
            
            if(map[s[left]] !== -Infinity){
                
                map[s[left]]++;
                
                if(map[s[left]] > valueGoal){
                    count++;
                }
                
            }
            left++
        }

        right++;
    }

    return output;
};
Replace the Substring for Balanced String