My code:
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int i = 0;
int j = 0;
int maxLen = 0;
for (; i < s.length(); i++) {
char curr = s.charAt(i);
if (map.containsKey(curr)) {
map.put(curr, map.get(curr) + 1);
maxLen = Math.max(maxLen, i - j + 1);
}
else {
if (map.size() <= 1) {
map.put(curr, 1);
maxLen = Math.max(maxLen, i - j + 1);
}
else {
while (map.size() >= 2) {
char pre = s.charAt(j);
int times = map.get(pre);
times--;
if (times == 0) {
map.remove(pre);
}
else {
map.put(pre, times);
}
j++;
}
map.put(curr, 1);
maxLen = Math.max(maxLen, i - j + 1);
}
}
}
return maxLen;
}
}
这道题目我以前竟然没有做过？？
自己写了出来，感觉配不上hard的称号。
和 longest substring with no repeating characters
一样的思路。
这里，key -> character
value -> counter
每当我发现，我需要插入一个新的字母，并且这个字母使得当前窗口unique character变为3 时，我就需要开始删减窗口。
左侧的j就开始移动，然后每移动一格，将该处的character counter--
如果 counter == 0, remove key from hash table
do while until map.size() < 2
然后做插入操作。
每个元素会被访问两次。
所以时间复杂度是 O(n)
空间复杂度是 O(n)
然后看答案，感觉有种解法更快，他只需要遍历一次数组，而不是两次。
My code:
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int maxLen = 0;
int j = 0;
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
map.put(curr, i);
if (map.size() > 2) {
int leftMost = Integer.MAX_VALUE;
for (Character c : map.keySet()) {
leftMost = Math.min(leftMost, map.get(c));
}
map.remove(s.charAt(leftMost));
j = leftMost + 1;
}
maxLen = Math.max(maxLen, i - j + 1);
}
return maxLen;
}
}
reference:
https://discuss.leetcode.com/topic/26640/simple-o-n-java-solution-easily-extend-to-k-characters
其实就是，value存的是最新的位置。
当我们发现 map.size() > 2时，将该窗口，最左侧的那个character找出来 (遍历当前map完成这个任务)
然后从hash table里面删除。
然后 j = leftMost + 1,这是新窗口的最左侧了。
然后可以更新maxLen
差不多就这个思路了。
Anyway, Good luck, Richardo! -- 09/18/2016
