Solution to the follow up


  • 2

    The basic approach is using sliding window. But then I realized that there is no need to record the times character occurs in the String. Since when the number of unique characters reaches the boundary, what we what to do is increase the left index to remove character until the number of unique characters reduce by 1. So we can directly store the final position the character occurs in the previous string and every time we remove the character with the smallest final position. Also we are scanning from small index to large index, the character with the smallest final position is the character we least recently encountered. This is similar to the idea of LRU Cache. Therefore, we can use LinkedHashMap to record the character. This solution will then solve the follow up like input string are streamed and still solve in O(n) time.

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if(s==null || s.length()==0 || k<=0) return 0;
            int len=s.length();
            int i=0, j=0;
            int maxLen=0;
            LinkedHashMap<Character,Integer> map=new LinkedHashMap<Character,Integer>();
            for(char x:s.toCharArray()){
                if(map.containsKey(x)){
                    map.remove(x);
                    map.put(x,j);
                }else{
                    if(map.size()==k){
                        maxLen=Math.max(maxLen,j-i);
                        char toRemove=map.keySet().iterator().next();
                        i=map.get(toRemove)+1;
                        map.remove(toRemove);
                    }
                    map.put(x,j);
                }
                j++;
            }
            maxLen=Math.max(maxLen,j-i);
            return maxLen;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.