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”.


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);  
        System.debug('mapOfChars > ' + mapOfChars);
        if (mapOfChars.size() == k+1){
            List<Integer> mapOfValues = mapOfChars.values();
            Integer leftMax = mapOfValues.get(0);
            left = leftMax + 1;
    List<Integer> charStartEnd = mapOfChars.values();
    return str.subString(charStartEnd.get(0)-1, charStartEnd.get(1));


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 )

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