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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: