Problem Name: 1234. Replace the Substring for Balanced String

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.


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". 



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

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

class Solution:
    def balancedString(self, s: str) -> int:
        cnt, i, res = {c: max(s.count(c) - len(s) // 4, 0) for c in 'QWER'}, 0, len(s)
        for j, c in enumerate(s):
            cnt[c] -= 1
            while i < len(s) and cnt[s[i]] < 0:
                cnt[s[i]] += 1
                i += 1
            if not any(cnt[c] > 0 for c in 'QWER'):
                res = min(res, j - i + 1)
        return res
Copy The Code & Try With Live Editor


s = "QQWE"




#1233 Leetcode Remove Sub-Folders from the Filesystem Solution in C, C++, Java, JavaScript, Python, C# Leetcode
#1235 Leetcode Maximum Profit in Job Scheduling Solution in C, C++, Java, JavaScript, Python, C# Leetcode