1234. Replace the Substring for Balanced String

You are given a string containing only 4 kinds of characters 'Q', 'W', 'E' and 'R'.

A string is said to be balancedif 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
  • contains only 'Q''W''E' and 'R'.

这道题说是给了一个只包含 QWER 四种字符的字符串,博主强烈怀疑出题者是重度的撸啊撸玩家,四个技能的快捷键用的溜。现在定义了一种平衡状态,就是每个字符出现的次数相等,这里可以替换任意长度的子串,问可以将字符串变为平衡状态时需要替换的最短子串长度,若给定字符串已经是平衡状态了,则返回0。这道题限定了给定字符串的长度是4的倍数(不然无论怎么替换,都不可能使得字符个数相等),那么为了达到平衡状态,每个字符出现次数必须是 n/4。由于替换的必须是一个子串,所以必须整体来考虑,这种玩子串求极值的题,一般无非就是 DP 或者滑动窗口来做,这里 DP 显然不合适,没有明显的状态转移的关系。而滑动窗口 Sliding Window 就天然适合这道题,因为每个子串就是滑动窗口。由于子串中的字符可以任意替换,所以我们并不 care 子串里具体有啥字符,需要关心的是替换后能否使得所有字符个数相等,那么子串以外的字符的个数就很关键了。

若子串以外某个字母的个数超过了 n/4,则无论怎么替换子串内的字符,该字母个数也不会减少,永远无法达到平衡状态,所以只有当子串以外的每个字符的出现次数都小于等于 n/4,替换子串才可以达到平衡。这里首先用个 HashMap 来统计给定字符串中每个字母的出现次数,然后就可以开始滑动窗口了,用变量i来控制窗口的右边界,left 来控制左边界。每当右边界扩大一位,就要在 HashMap 中将该字母的映射值减1,因为需要统计窗口之外的字符出现次数。接下来用一个 while 循环来收缩窗口,一般的滑动窗口的左边界不能超过右边界,这里由于滑动窗口的大小可以是0,而且需要滑动窗口的大小越小越好,则左边界的限制条件可以改为 left 小于n,不用担心窗口大小为负,因为还有其他的限制条件,就是窗口以外的所有字符的出现次数均小于等于 n/4。满足这些条件的话,就可以用窗口长度来更新结果 res 了,此时缩小左边界,将其字母的映射值自增1,然后 left 自增1即可,参见代码如下:

class Solution {
public:
    int balancedString(string s) {
        int n = s.size(), res = n, left = 0, k = n / 4;
        unordered_map<char, int> m;
        for (char c : s) ++m[c];
        for (int i = 0; i < n; ++i) {
            --m[s[i]];
            while (left < n && m['Q'] <= k && m['W'] <= k && m['E'] <= k && m['R'] <= k) {
                res = min(res, i - left + 1);
                ++m[s[left++]];
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1234

参考资料:

https://leetcode.com/problems/replace-the-substring-for-balanced-string/

https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window

LeetCode All in One 题目讲解汇总(持续更新中…)

喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation