# 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
```