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

Tip:

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

Ideas:

  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