340 Longest Substring with At Most K Distinct Characters

1. Question

Given a string, find the length of the longest substring T that contains at mostkdistinct characters.
For example, Given s =“eceba”and k = 2,
T is "ece" which its length is 3.

2. Implementation

(1) Two Pointer + Hash
1
class Solution {
2
public int lengthOfLongestSubstringKDistinct(String s, int k) {
3
if (s.length() <= k) {
4
return s.length();
5
}
6
7
int maxLen = 0, start = 0, end = 0, count = 0;
8
int[] map = new int[256];
9
10
while (end < s.length()) {
11
if (map[s.charAt(end)] == 0) {
12
++count;
13
}
14
++map[s.charAt(end)];
15
++end;
16
17
while (count > k) {
18
if (map[s.charAt(start)] == 1) {
19
--count;
20
}
21
--map[s.charAt(start)];
22
++start;
23
}
24
maxLen = Math.max(maxLen, end - start);
25
}
26
return maxLen;
27
}
28
}
Copied!

3. Time & Space Complexity

Two Pointer + Hash: 时间复杂度O(n), 空间复杂度O(1)