Question

1234. 替换子串得到平衡字符串

English Version

题目描述

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

 

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

 

示例 1：

输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。 

示例 4：

输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

 

提示：

• 1 <= s.length <= 10^5
• s.length 是 4 的倍数
• s 中只含有 'Q', 'W', 'E', 'R' 四种字符

解法

方法一：计数 + 双指针

我们先用一个哈希表或数组 cnt 统计字符串 $s$ 中每个字符的数量，如果所有字符的数量都不超过 $n/4$，那么字符串 $s$ 就是平衡字符串，直接返回 $0$。

否则，我们使用双指针 $j$ 和 $i$ 分别维护窗口的左右边界，初始时 $j = 0$。

接下来，从左到右遍历字符串 $s$，每次遍历到一个字符，就将该字符的数量减 $1$，然后判断当前窗口是否满足条件，即窗口外的字符数量都不超过 $n/4$。如果满足条件，那么就更新答案，然后将窗口的左边界右移，直到不满足条件为止。

最后，返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 $s$ 的长度；而 $C$ 是字符集的大小，本题中 $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
}