Longest Substring with At Most K Distinct Characters

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

Have you met this question in a real interview? 

Yes

Example

For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge

O(n), n is the size of the string s.

public class Solution {

    /**

     * @param s : A string

     * @return : The length of the longest substring 

     *           that contains at most k distinct characters.

     */

    public int lengthOfLongestSubstringKDistinct(String s, int k) {

        // write your code here

        if(k == 0) return 0;

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();

        int maxLen = 0, start = 0;

        for(int i = 0; i < s.length(); i++){

            char c = s.charAt(i);

            if(!map.containsKey(c)){

                if(map.size() == k){

                    maxLen = Math.max(i - start, maxLen);

                    for(int j = start; j < i; j++){

                        char key = s.charAt(j);

                        map.put(key, map.get(key)-1);

                        if(map.get(key) == 0){

                            start = j + 1;

                            map.remove(key);

                            break;

                        }

                    }

                }    

                map.put(c, 1);

                

            } else {

                map.put(c, map.get(c)+1);

            }

        }

        maxLen = Math.max(maxLen, s.length() - start);

        return maxLen;

    }

}