Last active
September 6, 2017 20:20
-
-
Save BiruLyu/457924c6ef22c37f9e10fcb3a521ba05 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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