leetcode 159: Longest Substring with At Most Two Distinct Characters
1465 ワード
Total Accepted: 1167 Total Submissions: 3961
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example,Given s =
[解析]
現在の2文字の数をHASHTABLEで記録する、新しい文字に遭遇した場合、startポインタの位置を新しいstart位置まで移動し、2文字のみを含む.この問題は考え方が簡単で、なぜかHARDと表記されている.もっと良い解があるかもしれませんが、extra spaceを使う必要はありません.
[code]
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example,Given s =
“eceba”
, T is "ece"which its length is 3. [解析]
現在の2文字の数をHASHTABLEで記録する、新しい文字に遭遇した場合、startポインタの位置を新しいstart位置まで移動し、2文字のみを含む.この問題は考え方が簡単で、なぜかHARDと表記されている.もっと良い解があるかもしれませんが、extra spaceを使う必要はありません.
[code]
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
//input check
if(s== null || s.length()==0) return 0;
Map<Character, Integer> map = new HashMap<Character, Integer>();
int start = 0;
int max = 0;
for(int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
map.put( c, map.get(c) + 1 );
} else if(map.size() < 2) {
map.put(c, 1);
} else {
while( (map.size()==2) && start<i) {
char temp = s.charAt(start);
int x = map.get(temp);
--x;
if(x==0) map.remove(s.charAt(start));
else map.put(s.charAt(start), x);
++start;
}
map.put(c,1);
}
max = Math.max(max, i-start+1);
}
return max;
}
}