-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_340.java
More file actions
49 lines (44 loc) · 1.35 KB
/
Copy pathP_340.java
File metadata and controls
49 lines (44 loc) · 1.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package leetcode.hard;
import java.util.LinkedHashMap;
import java.util.Map;
public class P_340 {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
final int[] count = new int[256];
int num = 0, i = 0, res = 0;
for (int j = 0; j < s.length(); j++) {
if (count[s.charAt(j)]++ == 0) {
num++;
}
while (num > k) {
if (--count[s.charAt(i)] == 0) {
num--;
}
i++;
}
res = Math.max(res, j - i + 1);
}
return res;
}
public int lengthOfLongestSubstringKDistinctLHM(String s, int k) {
if (k == 0) {
return 0;
}
int lo = 0, hi = 0, max = 0;
final int n = s.length();
final Map<Character, Integer> map = new LinkedHashMap<>();
while (hi < n) {
final char curr = s.charAt(hi);
if (map.containsKey(curr) || map.size() < k) {
map.remove(curr);
map.put(curr, hi);
max = Math.max(max, hi++ - lo + 1);
} else {
final Character leftmost = map.keySet().iterator().next();
lo = map.get(leftmost);
map.remove(leftmost);
lo++;
}
}
return max;
}
}