# Longest Substring with At Most K Distinct Characters

## Question

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

Example

For example, Given s = `"eceba"`, `k = 3`,

T is `"eceb"` which its length is `4`.

Challenge

O(n), n is the size of the string s.

Tags

String Two Pointers LintCode Copyright Hash Table

Related Problems

Medium Longest Substring Without Repeating Characters

## Solution

Two Pointers

``````public class Solution {
/**
* @param s : A string
* @return : The length of the longest substring
*           that contains at most k distinct characters.
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int strLength = s.length();
int i = 0;
int j = 0;
int ans = Integer.MIN_VALUE;

for (i = 0; i < strLength; i++) {
while (j < strLength) {
char ch_j = s.charAt(j);
if (!map.containsKey(ch_j)) {
if (map.size() == k) {
break;
}
map.put(ch_j, 1);
} else {
map.put(ch_j, map.get(ch_j) + 1);
}
j++;
}
ans = Math.max(ans, j - i);
char ch_i = s.charAt(i);
if (map.containsKey(ch_i)) {
if (map.get(ch_i) - 1 == 0) {
map.remove(ch_i);
} else {
map.put(ch_i, map.get(ch_i) - 1);
}
}

}

return ans;
}
}``````

(Preferred Implementation)* Sliding Window - Two Pointers (16ms, 48.48%)

O(n) time, O(n) space

``````class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
HashMap<Character, Integer> count = new HashMap<>();
int n = s.length();
int firstIdx = 0;
char[] chs = s.toCharArray();

int longest = 0;

for (int i = 0; i < n; i++) {
count.put(chs[i], count.getOrDefault(chs[i], 0) + 1);
while (count.size() > k) {
count.put(chs[firstIdx], count.get(chs[firstIdx]) - 1);
if (count.get(chs[firstIdx]) == 0) {
count.remove(chs[firstIdx]);
}
firstIdx++;
}
longest = Math.max(longest, i - firstIdx + 1);
}
return longest;
}
}``````

## Follow Up

The interviewer may say that the string is given as a steam. In this situation, we can't maintain a "left pointer" as the classical O(n) hashmap solution.

Instead of recording each char's count, we keep track of char's last occurrence. If you consider k as constant, it is also a O(n) algorithm.

`inWindow` keeps track of each char in window and its last occurrence position

TreeMap + HashMap - O(nlogk)

``````   public class Solution {
public int lengthOfLongestSubstringKDistinct(String str, int k) {
if (str == null || str.isEmpty() || k == 0) {
return 0;
}
TreeMap<Integer, Character> lastOccurrence = new TreeMap<>();
Map<Character, Integer> inWindow = new HashMap<>();
int j = 0;
int max = 1;
for (int i = 0; i < str.length(); i++) {
char in = str.charAt(i);
while (inWindow.size() == k && !inWindow.containsKey(in)) {
int first = lastOccurrence.firstKey();
char out = lastOccurrence.get(first);
inWindow.remove(out);
lastOccurrence.remove(first);
j = first + 1;
}
//update or add in's position in both maps
if (inWindow.containsKey(in)) {
lastOccurrence.remove(inWindow.get(in));
}
inWindow.put(in, i);
lastOccurrence.put(i, in);
max = Math.max(max, i - j + 1);
}
return max;
}
}``````

Another Implementation based on LinkedHashMap - O(n)

``````class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int left = 0;
int max = 0;
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.remove(c);
}
map.put(c, i);
if(map.size() > k) {
char key = map.keySet().iterator().next();
left = map.get(key) + 1;
map.remove(key);
}
max = Math.max(max, i - left + 1);
}
return max;
}
}``````

Last updated