動機

window中的東西可以亂生!!

Problem

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: 0Explanation: s is already balanced.

Example 2:

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

Example 3:

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

Example 4:

Input: s = "QQQQ"Output: 3Explanation: 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'.

Sol

window中的東西可以亂生，所以只要外面不超標的話就可以用window把string給平衡掉

class Solution:
    def balancedString(self, s: str) -> int:
        cnts, base = Counter(s), len(s)//4
        if all([cnts[x] == base for x in "QWER"]):
            return 0
        
        i = 0
        ret = float('inf')
        for j,c in enumerate(s):
            cnts[c] -= 1
            while i <= j and all([base >= cnts[x] for x in "QWER"]): # string will be balanced
                ret = min(ret, j-i+1)
                cnts[s[i]] += 1
                i += 1
        return ret