159 Longest Substring with At Most Two Distinct Characters

1. Question

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

2. Implementation

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

3. Time & Space Complexity

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