1234.md

1234. Replace the Substring for Balanced String

Solution 1 (time O(n), space O(1))

class Solution(object):
    def balancedString(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        cnt = collections.Counter(s)
        target = n // 4

        def check():
            if cnt["Q"] > target or cnt["W"] > target or cnt["E"] > target or cnt["R"] > target:
                return False
            return True
        
        if check():
            return 0
        ans = n
        p2 = 0
        for p1, c in enumerate(s):
            while p2 < n and not check():
                cnt[s[p2]] -= 1
                p2 += 1
            if not check():
                break
            ans = min(ans, p2 - p1)
            cnt[c] += 1
        return ans