Leetcode-每日一题1234. 替换子串得到平衡字符串(滑动窗口 + 哈希表)

简介: 简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。https://blog.csdn.net/weixin_46618592/article/details/129004869?spm=1001.2014.3001.5502

在这里插入图片描述
题目链接:https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/

思路

题目意思

这题意思是一个只含有[Q, W, E, R] 四个字符的字符串s且长度一定是 4的倍数, 需要你通过替换子串,使他变成一个「平衡字符串」,也就是字符串s内四个字符的数量都相等。

首先要仔细审题,我刚开始是以为计算需要替换的字符的数量,秒wa,仔细阅读发现是替换连续子串,需要找到一个最小长度的替换连续子串,第一反应就是滑动窗口或者双指针。

算法小课堂
滑动窗口:滑动窗口是双指针的一种特例,可以称为左右指针,在任意时刻,只有一个指针运动,而另一个保持静止。 滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。
滑动窗口的时间复杂度是线性的,时间复杂度一般为O(n),滑动窗口的左右边界都不会向左滑动,向左滑动等于走回头路,是一种回溯的算法,很可能会陷入死循环。滑动窗口是一种全遍历问题,一定会遍历到末尾的。

方法:滑动窗口 + 哈希表

刚开始我们用哈希表统计出四个字符的数量,我们需要满足「平衡字符串」,所以定义一个 check函数 判断四个字符数量小于等于 n / 4。

  • 如果原始的 s 就是 「平衡字符串」,则返回 0。
  • 如果不是,接下来就是用滑动窗口来遍历字符串,找到待替换子串,来维护区间 [l,r) :

    • 当前 l 指针不动, 通过内循环移动 r 指针,循环条件 r 指针需小于字符串s长度并且check函数满足,直到找到待替换子串。
    • 如果找到了使得条件被满足的 r,我们用 r−l 来更新答案 ans,当前 r 指针不动,并使得 l向右移动一个单位进行下一次枚举,通过外循环移动 l 指针, 循环条件 l 指针需小于字符串s长度,使当前代替换子串合法并且最小。
    • 直到 r 指针移动到大于等于字符串s长度的位置,且check函数不满足,退出循环。

代码示例

func balancedString(s string) int {
    n := len(s)
    mp := make(map[byte]int)
    for _, v := range s {
        mp[byte(v)]++
    }
    // 判断当前字符串是否是平衡字符串
    check := func() bool {
        if mp['Q'] > n / 4 || mp['W'] > n / 4 ||
        mp['E'] > n / 4 || mp['R'] > n / 4 {
            return false
        }
        return true
    }
    if check() {
        return 0
    }
    r, ans := 0, len(s)
    // 滑动窗口
    for l, c := range s {
        for r < n && !check() {
            mp[s[r]]--
            r++
        }
        // 如果上面循环是 r >= n 条件退出,
        // 表示现在的连续子串是不满足替换条件的,可以直接退出,避免影响正确答案
        if !check() {
            break
        }
        ans = min(ans, r - l)
        mp[byte(c)]++
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

在这里插入图片描述

复杂度分析

  • 时间复杂度:O(n),其中n表示字符串s的长度,记录四个字符的数量需要遍历字符串s,所需时间为O(n),滑动窗口时间是线性的,所以所需时间也为O(n)。
  • 空间复杂度:O(1),不需要额外申请空间。
目录
相关文章
|
1月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
1月前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
存储 编译器 Linux
18 0
|
12天前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
1月前
|
存储
leetcode2744. 最大字符串配对数目
leetcode2744. 最大字符串配对数目
17 0
|
1月前
|
机器学习/深度学习 NoSQL Shell
力扣刷题-翻转字符串
力扣刷题-翻转字符串
12 1
|
1月前
|
算法 索引
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
21 0
|
22天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记