1234. Replace the Substring for Balanced String #

Problem #

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'.

Problem Summary #

There is a string of length n that contains only the four characters ‘Q’, ‘W’, ‘E’, and ‘R’. If, in this string, all four characters appear exactly n/4 times, then it is a “balanced string”. Given such a string s, make the original string s become a “balanced string” by “replacing one substring”. You may replace it with any other string of the same length as the “substring to be replaced”. Return the minimum possible length of the substring to be replaced. If the original string itself is a balanced string, return 0.

Notes:

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

Solution Approach #

Given a string, output the minimum length of the replacement substring needed to turn this string into a “balanced string” (the replacement can only replace one contiguous substring, not individual letters). The definition of a “balanced string” is: in the string, ‘Q’, ‘W’, ‘E’, and ‘R’ each appear exactly len(s)/4 times.
This is a sliding window problem. First count the frequencies of the 4 letters and compute k = len(s)/4. Each time the sliding window moves to the right, decrement the frequency of the character at the right boundary by 1, until it reaches a point where the frequencies of all letters are ≤ k. At this point, the frequencies of the letters outside the window are all ≤ k. Now we only need to transform the string inside the window. However, this window may still contain letters whose original frequency is less than k; if they can be removed, the window can be reduced further. So continue moving the left boundary and test whether, after moving the left boundary, the frequencies of all letters are still ≤ k. Take the minimum value among all window movements; this is the final answer.
For example: "WQWRQQQW". There are 3 ws, 4 Qs, 1 R, and 0 Es. The final balanced state is 2 of each letter, so we need to take out 1 W and 2 Qs and replace them. That is, we need to find the shortest string containing 1 W and 2 Qs. The sliding window can solve exactly this problem. Slide to the right until "WQWRQ" and stop; at this time, the frequencies of all letters outside the window are ≤ k. This window contains the extra 1 W and 1 R. W can be removed, so the string to replace is "QWRQ". R cannot be removed (because we need to find a string containing 1 W and 2 Qs). Keep sliding the window until the end. In this example, the shortest string is actually at the end, "QQW".

Code #


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
}