Algorithm
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".
Constraints:
n == s.length
4 <= n <= 105
n
is a multiple of4
.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
Input
Output