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
每當(dāng)我發(fā)現(xiàn)，我需要插入一個新的字母快毛，并且這個字母使得當(dāng)前窗口unique character變?yōu)? 時格嗅，我就需要開始刪減窗口番挺。
左側(cè)的j就開始移動，然后每移動一格屯掖，將該處的character counter--
如果 counter == 0, remove key from hash table
do while until map.size() < 2
然后做插入操作玄柏。
每個元素會被訪問兩次。
所以時間復(fù)雜度是 O(n)
空間復(fù)雜度是 O(n)
然后看答案贴铜，感覺有種解法更快粪摘，他只需要遍歷一次數(shù)組辖所，而不是兩次掘殴。
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存的是最新的位置净嘀。
當(dāng)我們發(fā)現(xiàn) map.size() > 2時轩褐，將該窗口椎咧，最左側(cè)的那個character找出來 (遍歷當(dāng)前map完成這個任務(wù))
然后從hash table里面刪除。
然后 j = leftMost + 1,這是新窗口的最左側(cè)了把介。
然后可以更新maxLen
差不多就這個思路了勤讽。
Anyway, Good luck, Richardo! -- 09/18/2016
