数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中平衡字符串的子字符串替换
假设我们有一个字符串，其中只包含 4 种字符 'Q'、'W'、'E' 和 'R'。如果字符串中的每个字符都出现了 n/4 次（其中 n 是字符串的长度），则该字符串是平衡的。找到可以替换为任何其他相同长度的字符串的子字符串的最小长度，以使原始字符串变得平衡。因此，如果 s = “QQWE”，则输出将为 1。这是因为我们可以将 Q 替换为 R，从而得到“RQWE”，它是平衡的。
如果字符串已经平衡，则返回 0。
要解决此问题，我们将遵循以下步骤：
- 创建一个映射 m
- 对于 s 中的每个字符，将字符的频率存储到映射中，n := s 的大小
- res := n，left := 0
- 对于 right 从 0 到 n – 1
- 将 m[s[right]] 减少 1
- 当 left < n 且 m[Q] <= n/4 且 m[W] <= n/4 且 m[E] <= n/4 且 m[R] <= n/4 时
- res := res 和 right – left + 1 的最小值
- 将 m[s[left]] 增加 1
- 将 left 增加 1
- 返回 res
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedString(string s) {
unordered_map <char, int> m;
for(int i = 0;i<s.size();i++)m[s[i]]++;
int n = s.size();
int res = n;
int left = 0;
for(int right = 0;right<n;right++){
m[s[right]]--;
while(left<n && m['Q']<=n/4 && m['W'] <=n/4 && m['E'] <=n/4 && m['R']<=n/4){
res = min(res, right - left + 1);
m[s[left]]+=1;
left++;
}
}
return res;
}
};
main(){
Solution ob;
cout << (ob.balancedString("QQEQ"));
}输入
"QQEQ"
输出
2
更新于: 2020 年 5 月 2 日
377 次查看
广告