Easy to understand Java solution using HashMap, and keep the 'last' index of an element


  • 0

    //Use one pointer i to iterate string s, and use a HashMap<Character, Integer> to store the element and its last appearance index
    import java.util.stream.*;

    '''public class Solution {

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
    	if (k == 0) { return k; }
    
    	int i = 0, max = 0, tempMax = 0;
    	final Integer ONE = Integer.valueOf(1);
    	Map<Character, Integer> map = new HashMap<>();
    
    	while (i < s.length()) {
    		char ch = s.charAt(i);
    		if (map.size() < k || (map.size() == k && map.containsKey(ch))) {
    			if (map.containsKey(ch)) {
    			    //If s.charAt(i) has not been visited, update the last appearance index
    				if (Integer.valueOf(i).compareTo(map.get(ch)) > 0) {
    					map.replace(ch, i);
    					tempMax++;
    				}
    			}
    			else {
    				map.put(ch, i);
    				tempMax++;
    			}
    			max = Math.max(max, tempMax);
    			i++;
    			
    		} else { 
    			// 'jump' is the least last appearance of an element in this map, so move the pointer i to jump + 1
    			IntStream stream = map.values().stream().mapToInt(Integer::intValue); // Use IntStream to get the jump value
    			int jump = stream.min().getAsInt() ;	
    			tempMax = i - jump -1 ;
    			i = jump + 1;
    			map.remove(s.charAt(jump));
    		}
    	}
    	return max;
    }
    

    }


Log in to reply
 

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