This is the 31st day of my participation in the August Text Challenge.More challenges in August

Difficulty: Medium

Topic describes

There is a string of n characters containing only ‘Q’, ‘W’, ‘E’, and ‘R’.

If all four characters occur exactly n/4 times in the string, it is a “balanced string.”


Given such a string s, make the original string S an “equilibrium string” by “replacing a substring”.

You can do this 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.

Returns 0 if the original string is itself a balanced string.

Example 1:

Input: s = "QWER" Output: 0 Explanation: S is already in equilibrium.Copy the code

Example 2:

Input: s = "QQWE" Output: 1 Explanation: We need to replace a 'Q' with an 'R' so that the resulting "RQWE" (or "QRWE") is balanced.Copy the code

Example 3:

Input: s = "QQQW" Output: 2 Explanation: We can replace the previous "QQ" with "ER".Copy the code

Example 4:

Input: s = "QQQQ" Output: 3 Explanation: We can replace the last 3 'Q' so that S = "QWER".Copy the code


1 <= s.length <= 10^5 s.length is a multiple of 4. S contains only 'Q', 'W', 'E', and 'R'Copy the code


  1. The conditions are perfect, but anyway, these are the only four characters.
  2. The substring that needs to be replaced is trapped inside a window, but it can also be outside the window
  3. Use the double pointer L R
  • Greedy thoughts update min_window_len every time they are legal
  • Use dictionaries (or arrays) to do your statistics
class Solution: def balancedString(self, s: str) -> int: n = len(s) if n <=0 or n%4 ! = 0: return 0 m = n // 4 dic = defaultdict(int) for c in s: dic[c] += 1 if dic['Q']==m and dic['W']==m and dic['E']==m and dic['R']==m: Return 0 min_window_len = n # for R in range(n): dic[s[R]] -= 1 while L <= R and dic['Q']<=m and dic['W']<=m and dic['E']<=m and dic['R']<=m: min_window_len = min(min_window_len, R - L + 1) dic[s[L]] += 1 L += 1 return min_window_lenCopy the code