[leetcode] 1234. Replace the Substring for Balanced String

[leetcode] 1234. Replace the Substring for Balanced String

Description

You are given a string containing only 4 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 the original string s balanced.

Return 0 if the string is already balanced.

Example 1:

Input: s = "QWER"Output: 0Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"Output: 1Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"Output: 2Explanation: We can replace the first "QQ" to "ER".

Example 4:

Input: s = "QQQQ"Output: 3Explanation: We can replace the last 3 'Q' to make s = "QWER".

Constraints:

1 <= s.length <= 10^5s.length is a multiple of 4s contains only ‘Q’, ‘W’, ‘E’ and ‘R’.

分析

题目的意思是：替换字符串的一部分使得字符串变成平衡字符串。这道题我以为统计一下字符的频率就行了，发现ac不了，没想到是子序列，不能是任意位置。用双指针法，i指向子串的左端，j指向字符串的右端，当i~j去掉的字符串区间。维护i到j这个最小区间就行了。

代码

class Solution: def balancedString(self, s: str) -> int: count = collections.Counter(s) n=len(s) res=n i=0 for j,ch in enumerate(s): count[ch]-=1 while(i

参考文献

​​[LeetCode] [Java/C++/Python] Sliding Window​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。