Neat HashMap based Sliding window solution with comments.


  • 0
    P

    The key idea here is to put the last occurence of any character seen so far in the map.

    public int lengthOfLongestSubstringKDistinct(String s, int k) { // not a hard one to understand.
    		if (k == 0)
    			return 0;
    		Map<Character, Integer> map = new HashMap<>(); // You can use char Array instead of map to speed up the process.
    		int j = 0, count = 0, max = 0;
    		for (int i = 0; i < s.length(); i++) {
    			char ch = s.charAt(i);
    			if (map.containsKey(ch)) {
    				map.put(ch, i); // track the last occurence of this character.
    			} else {
    				if (count < k) {
    					map.put(ch, i);
    					count++;
    				} else {
    					while (count >= k) {
    						if (map.get(s.charAt(j)) == j) {// Is this last occurence of this character ?
    							map.remove(s.charAt(j));
    							count--;
    						}
    						j++;
    					}
    					map.put(ch, i); // Safe to put this character now.
    					count++;
    				}
    			}
    			if (i - j + 1 > max)
    				max = i - j + 1;
    		}
    		return max;
    
    	}

Log in to reply
 

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