# LeetCode: 1234. 替换子串得到平衡字符串¶

## 1、题目描述¶

输入：s = "QWER"



输入：s = "QQWE"



输入：s = "QQQW"



输入：s = "QQQQ"



• $1 <= s.length <= 10^5$
• s.length 是 4 的倍数
• s 中只含有 'Q', 'W', 'E', 'R' 四种字符

## 2、解题思路¶

• 贪心法

• 哪个区间能够通过替换子串得到平衡串呢？只要出了当前区域的字符串，QWER的数量都少于总长度的四分之一

设置两个指针，left和right，闭区间，分别指能够替换的左右位置

-》然后left减到0，不断的更新right

class Solution:
def balancedString(self, s: str) -> int:
length = len(s)
average = length // 4

count = [0] * 4
mapping_index = {"Q": 0, "W": 1, "E": 2, "R": 3, }

left = 0
right = length - 1
while left < length:
if count[mapping_index[s[left]]] + 1 <= average:
count[mapping_index[s[left]]] += 1
left += 1
else:
break

while right >= 0 and right >= left:
if count[mapping_index[s[right]]] + 1 <= average:
count[mapping_index[s[right]]] += 1
right -= 1
else:
break

ans = right - left + 1

while left >= 0:
left -= 1
count[mapping_index[s[left]]] -= 1
while right >= 0 and right >= left:
if count[mapping_index[s[right]]] + 1 <= average:
count[mapping_index[s[right]]] += 1
right -= 1
else:
break
ans = min(ans, right - left + 1)

return ans