1234 Replace the Substring for Balanced String 更换子串得到平衡字符串
Description:
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:
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 <= 10^5
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.
标题形貌：
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
如果在该字符串中，这四个字符都恰恰出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个如许的字符串 s，请通过「更换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待更换子串」长度类似的 任何 其他字符串来完成更换。
请返回待更换子串的最小大概长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例：
示例 1：
输入：s = "QWER"
输出：0
表明：s 已经是平衡的了。
示例 2：
输入：s = "QQWE"
输出：1
表明：我们必要把一个 'Q' 更换成 'R'，如许得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：
输入：s = "QQQW"
输出：2
表明：我们可以把前面的 "QQ" 更换成 "ER"。
示例 4：
输入：s = "QQQQ"
输出：3
表明：我们可以更换后 3 个 'Q'，使 s = "QWER"。
提示：
1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符
思绪：
滑动窗口
先统计全部字符(QWER)的出现次数, 如果出现次数刚好都是字符串长度的 1/4, 分析不必要更换直接返回 0
然后利用滑动窗口, 窗口中的值要包管全部字符出现次数可以或许用来更换
也就是说减去滑动窗口中字符的出现次数, 剩下的字符出现次数必要都小于字符串长度的 1/4
时间复杂度为 O(n), 空间复杂度为 O(1)
代码:
C++: |
