Longest Substring with At Most K Distinct Characters
Given a string s, find the length of the longest substring T that contains at most k distinct characters.
Have you met this question in a real interview? Yes
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 Expand
String Two Pointers LintCode Copyright Hash Table
思路
- 第一个是leetcode的题,第二个解释lintcode上的题,有小差别,leetcode这个是后来写的,优美一些
- 窗口型指针
- 注意以下,不是必须k distinct而是k个以下就可以,所以有了以下代码
if (map.size() == k + 1) {
max = Math.max(max, length - 1);
} else {
max = Math.max(max, length);
}
- 因为如果达到了k,那么就要减掉多余的一个,但是如果是因为j达到上限,说明还只是k个以下,就不用减
Leetcode
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int i = 0;
int j = 0;
int maxLen = 1;
int len = 0;
int n = s.length();
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (i = 0; i < n; i++) {
while (j < n && map.size() < 3) {
char tail = s.charAt(j++);
if (map.containsKey(tail)) {
map.put(tail, map.get(tail) + 1);
} else {
map.put(tail, 1);
}
len++;
if (map.size() <= 2) {
maxLen = Math.max(maxLen, len);
}
if (j == n) {
return maxLen;
}
}
len--;
char head = s.charAt(i);
map.put(head, map.get(head) - 1);
if (map.get(head) == 0) {
map.remove(head);
}
}
return maxLen;
}
}
Lintcode
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) {
// write your code here
if (s == null || s.length() == 0 || k <= 0) {
return 0;
}
if (s.length() <= k) {
return s.length();
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int i = 0;
int j = 0;
int length = 0;
int max = 0;
for (i = 0; i < s.length(); i++) {
while (map.size() <= k && j < s.length()) {
char cur = s.charAt(j++);
if (map.containsKey(cur)) {
map.put(cur, map.get(cur) + 1);
} else {
map.put(cur, 1);
}
length++;
}
if (map.size() == k + 1) {
max = Math.max(max, length - 1);
} else {
max = Math.max(max, length);
}
char deletechar = s.charAt(i);
int times = map.get(deletechar);
if (times == 1) {
map.remove(deletechar);
} else {
map.put(deletechar, map.get(deletechar) - 1);
}
length--;
}
return max;
}
}