刷题参考:https://blog.csdn.net/IBelieve2016/article/details/104544763
#include<iostream>
#include<vector>
#include <unordered_map>
#include<string>
using namespace std;
/*
Given a string, find the length of the longest substring T
that contains at most k distinct characters.
包含k个不同字符的最长子串
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.
用一个start纪录字符串开始的位置
charmap:纪录当前是否已经出现字符 ,(具有去重的作用)
统计charmap个数,即从start至当前位置具有多少个不同字符。
max(res,i-start+1)
*/
int solution(string s,int k){
int start=0,res=0;
unordered_map<char,int> charmap;
for(int i=0;i<s.size();i++){
//纪录当前存在的字符以及频数
charmap[s[i]]++;
//当不同字符的数量大于k,则移动start
while(charmap.size()>k){
//start位置的值在hash中值的频数-1
charmap[s[start]]--;
//如果等于0则将该值移除
if(charmap[s[start]]==0){
charmap.erase(s[start]);
}
start++;
}
res=max(res,i-start+1);
}
return res;
}
int main(){
string s="eceba";
int k=2;
cout<<solution(s,k);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)