Question

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 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 <= 105
• n is a multiple of 4.
• s contains only 'Q', 'W', 'E', and 'R'.

Solutions

Solution 1: Counting + Two Pointers

First, we use a hash table or array cnt to count the number of each character in string $s$. If the count of all characters does not exceed $n/4$, then the string $s$ is balanced, and we directly return $0$.

Otherwise, we use two pointers $j$ and $i$ to maintain the left and right boundaries of the window, initially $j = 0$.

Next, we traverse the string $s$ from left to right. Each time we encounter a character, we decrease its count by $1$, then we check whether the current window meets the condition, that is, the count of characters outside the window does not exceed $n/4$. If the condition is met, we update the answer, then move the left boundary of the window to the right until the condition is not met.

Finally, we return the answer.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Where $n$ is the length of the string $s$; and $C$ is the size of the character set, in this problem $C = 4$.

class Solution:
  def balancedString(self, s: str) -> int:
    cnt = Counter(s)
    n = len(s)
    if all(v <= n // 4 for v in cnt.values()):
      return 0
    ans, j = n, 0
    for i, c in enumerate(s):
      cnt[c] -= 1
      while j <= i and all(v <= n // 4 for v in cnt.values()):
        ans = min(ans, i - j + 1)
        cnt[s[j]] += 1
        j += 1
    return ans

class Solution {
  public int balancedString(String s) {
    int[] cnt = new int[4];
    String t = "QWER";
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      cnt[t.indexOf(s.charAt(i))]++;
    }
    int m = n / 4;
    if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) {
      return 0;
    }
    int ans = n;
    for (int i = 0, j = 0; i < n; ++i) {
      cnt[t.indexOf(s.charAt(i))]--;
      while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) {
        ans = Math.min(ans, i - j + 1);
        cnt[t.indexOf(s.charAt(j++))]++;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int balancedString(string s) {
    int cnt[4]{};
    string t = "QWER";
    int n = s.size();
    for (char& c : s) {
      cnt[t.find(c)]++;
    }
    int m = n / 4;
    if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) {
      return 0;
    }
    int ans = n;
    for (int i = 0, j = 0; i < n; ++i) {
      cnt[t.find(s[i])]--;
      while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) {
        ans = min(ans, i - j + 1);
        cnt[t.find(s[j++])]++;
      }
    }
    return ans;
  }
};

func balancedString(s string) int {
  cnt := [4]int{}
  t := "QWER"
  n := len(s)
  for i := range s {
    cnt[strings.IndexByte(t, s[i])]++
  }
  m := n / 4
  if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m {
    return 0
  }
  ans := n
  for i, j := 0, 0; i < n; i++ {
    cnt[strings.IndexByte(t, s[i])]--
    for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m {
      ans = min(ans, i-j+1)
      cnt[strings.IndexByte(t, s[j])]++
      j++
    }
  }
  return ans
}