1234. Replace the Substring for Balanced String

1234. Replace the Substring for Balanced String #

题目 #

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

Example 4:

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

Constraints:

  • 1 <= s.length <= 10^5
  • s.length 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.length <= 10^5
  • s.length 是 4 的倍数
  • s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

解题思路 #

  • 给出一个字符串,要求输出把这个字符串变成“平衡字符串”的最小替换字符串的长度(替换只能替换一串,不能单个字母替换)。“平衡字符串”的定义是:字符串中,‘Q’‘W’‘E’‘R’,出现的次数当且仅当只有 len(s)/4 次。
  • 这一题是滑动窗口的题目。先统计 4 个字母的频次并计算出 k = len(s)/4 。滑动窗口向右滑动一次,对应右窗口的那个字母频次减 1,直到滑到所有字母的频次都 ≤ k 的地方停止。此时,窗口外的字母的频次都 ≤ k 了。这是只要变换窗口内字符串即可。但是这个窗口内还可能包含本来频次就小于 k 的字母,如果能把它们剔除掉,窗口可以进一步的减少。所以继续移动左边界,试探移动完左边界以后,是否所有字母频次都 ≤ k。在所有窗口移动过程中取出最小值,即为最终答案。
  • 举个例子:"WQWRQQQW"w 有 3 个,Q 有 4 个,R 有 1 个,E 有 0 个。最后平衡状态是每个字母 2 个,那么我们需要拿出 1 个 W 和 2 个 Q 替换掉。即要找到一个最短的字符串包含 1 个 W 和 2 个 Q。滑动窗口正好可以解决这个问题。向右滑到 "WQWRQ" 停止,这时窗口外的所有字母频次都 ≤ k 了。这个窗口包含了多余的 1 个 W,和 1 个 RW 可以踢除掉,那么要替换的字符串是 "QWRQ"R 不能踢除了(因为要找包含 1 个 W 和 2 个 Q 的字符串) 。窗口不断的滑动,直到结束。这个例子中最小的字符串其实位于末尾,"QQW"

代码 #


package leetcode

func balancedString(s string) int {
	count, k := make([]int, 128), len(s)/4
	for _, v := range s {
		count[int(v)]++
	}
	left, right, res := 0, -1, len(s)
	for left < len(s) {
		if count['Q'] > k || count['W'] > k || count['E'] > k || count['R'] > k {
			if right+1 < len(s) {
				right++
				count[s[right]]--
			} else {
				break
			}
		} else {
			res = min(res, right-left+1)
			count[s[left]]++
			left++
		}
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者