Keshawn_lu's Blog

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

滑动窗口
字数统计: 589阅读时长: 2 min
2023/02/13 Share

题目简介：

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路：

首先，若原始字符串已经满足要求，则直接返回0即可。

否则，我们需要找到替换的字符串。

我们可以发现，当替换字符串外的字符都> s.size() / 4时，则无论怎么替换，都不能满足要求。

所以反过来说，当替换字符串外的字符都<= s.size() / 4时，则可以通过替换，满足要求。

因此我们利用滑动窗口，设替换字符串的左右端点为left, right。

我们枚举右端点，并通过替换字符串外的字符来判断[left, right]是否为可替换字符串，若是，则用min(res, right - left + 1)来更新答案，并向右移动left，来缩短替换字符串的长度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int balancedString(string s) {

        unordered_map<char, int> count;

        int sum = s.size() / 4;

        for(auto& c : s)
            count[c]++;

        if(count['Q'] == sum && count['W'] == sum && count['E'] == sum && count['R'] == sum)
            return 0;
        
        int res = s.size();

        //枚举右端点  [left, right]
        for(int right = 0, left = 0; right < s.size(); right++){

            count[s[right]]--;

            while(count['Q'] <= sum && count['W'] <= sum && count['E'] <= sum && count['R'] <= sum){

                res = min(res, right - left + 1);

                count[s[left]]++;
                left++;
            }
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网