Friday, December 26, 2014

Longest Substring with At Most Two Distinct Characters (LeetCode HashMap)

Question: 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.

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