Apex Coding Interview Challenge #11

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

For example, given s = “abcba” and k = 2, the longest substring with k distinct characters is “bcb”.

Solution

public static String getLongestSubstringDistinct(String str, Integer k){
    Integer n = str.length();
    
    Integer left = 0;
    Integer right = 0;
    
    Map<Integer, Integer> mapOfChars = new Map<Integer, Integer>();
    
    while (right < n){
        if (mapOfChars.size() < k+1){
            if (!mapOfChars.containsKey(str.charAt(right))){ 
               mapOfChars.put(str.charAt(right), right);           
            } else if (right-mapOfChars.get(str.charAt(right))<=1){
                mapOfChars.put(str.charAt(right), right);  
            }
              
            right++;
        }
        System.debug('mapOfChars > ' + mapOfChars);
        
        if (mapOfChars.size() == k+1){
            List<Integer> mapOfValues = mapOfChars.values();
            mapOfValues.sort();
            Integer leftMax = mapOfValues.get(0);
            
            mapOfChars.remove(str.charAt(leftMax));
            left = leftMax + 1;
        }
    }
    
    List<Integer> charStartEnd = mapOfChars.values();
    charStartEnd.sort();
    return str.subString(charStartEnd.get(0)-1, charStartEnd.get(1));
}

Testing

System.debug(getLongestSubstringDistinct('abcba', 2)); //bcb
System.debug(getLongestSubstringDistinct('zxybobc', 2)); //bob