1234.md

Replace the Substring for Balanced String

Description

link

---

Solution

• 右边保持滑动，左边保存两个变量l，r分别代表从l，r到右边区间内存在K个以及K-1个不同整数的区间
• 此时答案即为加上r-l即可

---

Code

O(n) O(n)

class Solution:
    def balancedString(self, s: str) -> int:
        cnt = collections.Counter(s)
        res = n = len(s)
        l = 0
        for r, c in enumerate(s):
            cnt[c] -= 1
            while l < n and all(n//4 >= cnt[c] for c in 'QWER'):
                res = min(r - l + 1, res)
                cnt[s[l]] += 1
                l += 1
        return res