Longest Substring with At Most K Distinct Characters
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
for(int i=0; i< s.length(); i ){
char cur = s.charAt(i);
while(j< s.length()){
if(cache.containsKey(s.charAt(j))){
int freq = cache.get(s.charAt(j));
cache.put(s.charAt(j), freq 1);
} else {
if(cache.size() == k){
//maxlen = Math.max(maxlen, j-i);
break;
}
cache.put(s.charAt(j), 1);
}
j ;
}
maxlen = Math.max(maxlen, j-i);
if(cache.get(cur) == 1){
cache.remove(cur);
} else {
cache.put(cur, cache.get(cur)-1);
}
}
Get one-to-one training from Google Facebook engineers
Top-notch Professionals
Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.
Customized Private Class
Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.