For example, Given s = “eceba”,
T is "ece" which its length is 3.
Idea: Use two pointers (left, right) to maintain a sliding window. Use a HashMap to cache the elements and their counts in the sliding window. If the HashMap has at most 2 keys, move the right pointer forward; otherwise move the left pointer forward until the HashMap has one empty spot to add another key. The loop ends when the right pointer reaches the end of the string s and the window is valid. Update the result whenever the right pointer moves forward, since moving the left pointer only decreases the window width.
Time: O(n) Space: O(n)
Code:
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s.length()<=2)
{
return s.length();
}
HashMap<Character,Integer> found=new HashMap<Character,Integer>();
int leftBound=0;
int result=0;
for(int i=0;i<s.length();i++)
{
char c=s.charAt(i);
if(found.containsKey(c))
{
found.put(c,found.get(c)+1);
}
else
{
while(found.size()==2)
{
char leftest=s.charAt(leftBound);
found.put(leftest,found.get(leftest)-1);
leftBound+=1;
if(found.get(leftest)==0)
{
found.remove(leftest);
}
}
found.put(c,1);
}
int sum=0;
for(int value:found.values())
{
sum+=value;
}
result=Math.max(result,sum);
}
return result;
}
}
No comments:
Post a Comment