Longest Substring with At Most K Distinct Characters

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.