Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save BiruLyu/457924c6ef22c37f9e10fcb3a521ba05 to your computer and use it in GitHub Desktop.
Save BiruLyu/457924c6ef22c37f9e10fcb3a521ba05 to your computer and use it in GitHub Desktop.
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() < 1) return 0;
int count = 0, end = 0, start = 0, res = 0;
int[] vector = new int[256];
char[] str = s.toCharArray();
while (end < str.length) {
if (vector[str[end++]]++ == 0) count++;
while (count > 2) {
if (--vector[str[start++]] == 0) count--;
}
res = Math.max(res, end - start);
}
return res;
}
}
/*
using hashset store at most 2 unique characters, however it is not easy to extend to k characters
using hashmap to store the last occurrence of each character coped with finding left most the character with the left most index
*/
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) return 0;
int start = 0;
int end = 0;
int res = 0;
//char[] dict = new char[2];
//HashSet<Character> dict = new HashSet<Character>();
HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
while( end < s.length()){
if (dict.size() <= 2){
dict.put(s.charAt(end), end);
end++;
}
if (dict.size() > 2) {
int leftMost = s.length();
for(int i : dict.values()){
leftMost = Math.min(leftMost, i);
}
dict.remove(s.charAt(leftMost));
start = leftMost + 1;
}
res = Math.max(res, end - start);
}
return res;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment