数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最多包含 K 个不同字符的最长子字符串
假设我们有一个字符串；我们需要计算包含最多 k 个不同字符的最长子字符串 T 的长度。
因此，如果输入类似于 s = "eceba"，k = 2，则输出将为 3，因为 T 是 "ece"，其长度为 3。
为了解决这个问题，我们将遵循以下步骤：
ans := 0
定义一个映射 m
n := s 的大小
x := 0
从初始化 j := 0、i := 0 开始，当 j < n 时，更新（将 j 增加 1），执行以下操作：
(将 m[s[j]] 增加 1)
如果 m[s[j]] 等于 1，则：
(将 x 增加 1)
当 (x > k 且 i <= j) 时，执行以下操作：
(将 m[s[i]] 减小 1)
如果 m[s[i]] 等于 0，则：
(将 x 减小 1)
(将 i 增加 1)
ans := ans 和 (j - i + 1) 的最大值
返回 ans
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
};
main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}输入
"eceba", 2
输出
3
更新于: 2020-07-21
1K+ 次查看
广告