Leetcode 1234:替换子串得到平衡字符串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1234:替换子串得到平衡字符串(超详细的解法!!!)

in leetcode with 0 comment

有一个只含有 '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"。

提示:

解题思路

因为是查找问题首先可以想到通过二分法来做,左边边界也非常好取l=0并且r=n,最关键的问题就是判断函数的书写。其实也非常简单,我们可以将每个大小看成是滑动窗口的大小x,例如:

W W E Q E R Q W Q W W R W W E R Q W E Q 
↑     ↑

此时我们可以统计窗口之外的所有字符出现次数k,我们需要计算它和len(s)//4大小关系。如果字符串出现次数都满足k <= len(s)//4,那么满足条件(因为如果k>len(s)//4的话,那么此时这个字符必然需要减少才能达到平衡,而减少的手段只能变成其他字符,而只有窗口中的字符才可以变化,所以。。。),返回true;否则,继续判断下一个窗口位置是不是满足条件(窗口向右滑动)。

这里在统计字符个数k的时候,为了提高查找速度,采用前缀和计算当前位置之前所有字符出现的次数的累加和,例如:

W W E Q E R Q W Q W W R W W E R Q W E Q 
      ↑
Q: 1    W: 3    E: 1    R: 0

那么此时的窗口起始位置是st,那么窗口的终点位置就是st+x,字符出现此时我们通过cnt字典存储,那么窗口之外的所有字符出现次数k就可以表示为cnt[n]-cnt[st+x]+cnt[st]

class Solution:
    def balancedString(self, s: str) -> int:
        n = len(s)
        cnt, avg = [None] * (n + 1), n//4
        cnt[0] = {'Q':0, 'W':0, 'E':0, 'R':0}
        for i, v in enumerate(s):
            cnt[i+1] = {k:v for k, v in cnt[i].items()}
            cnt[i+1][v] += 1
        
        def check(x):
            for st in range(n - x + 1):
                t = {k:cnt[n][k] - cnt[st+x][k] + cnt[st][k] for k in cnt[0].keys()}
                if all(avg >= t[x] for x in 'QWER'):
                    return True
            return False
            
        l, r = 0, n
        while l < r:
            mid = l + r >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1   
        return l

实际上这个问题还有一种更加简洁的做法,就是双指针。其实通过上面的解析,我们已经知道了只要每个字符个数小于等于len(s)//4就可以满足条件,那么就是可以通过建立两个指针ij遍历所有的窗口大小,判断满足条件的最小窗口即可。

class Solution:
    def balancedString(self, s: str) -> int:
        cnt = collections.Counter(s)
        res = n = len(s)
        i, avg = 0, n//4
        for j, c in enumerate(s):
            cnt[c] -= 1
            while i < n and all(avg >= cnt[x] for x in 'QWER'):
                res = min(res, j - i + 1)
                cnt[s[i]] += 1
                i += 1
        return res

reference:

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

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses