Leetcode 1351 Solution

This article provides solution to leetcode question 1351 (replace-the-substring-for-balanced-string)
Categories:
Tags:
Access this page by simply typing in "lcs 1351" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/replace-the-substring-for-balanced-string

Solution

class Solution:
    def balancedString(self, s: str) -> int:
        cnts = collections.defaultdict(int)
        for ch in s:
            cnts[ch] += 1

        needs = {
            "Q": max(cnts['Q'] - len(s) // 4, 0),
            "W": max(cnts['W'] - len(s) // 4, 0),
            "E": max(cnts['E'] - len(s) // 4, 0),
            "R": max(cnts['R'] - len(s) // 4, 0),
        }

        curr = collections.defaultdict(int)
        l = 0
        r = 0
        curr[s[0]] += 1

        ans = len(s)

        while True:
            is_valid = (
                curr["Q"] >= needs["Q"]
                and curr["W"] >= needs["W"]
                and curr["E"] >= needs["E"]
                and curr["R"] >= needs["R"]
            )

            if is_valid:
                ans = min(ans, r - l + 1)

                if l <= r:
                    ch = s[l]
                    curr[ch] -= 1
                    l += 1
                else:
                    break
            else:
                if r < len(s) - 1:
                    r += 1
                    ch = s[r]
                    curr[ch] += 1
                else:
                    break

        return ans