Sunday, January 11, 2015

LeetCode 159: Longest Substring with At Most Two Distinct Characters

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.
public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        // Adopt sliding window
        // start --- the starting position of the window
        // i --- the first distinct character after the window
        // This algorithm is easy for understanding but need additional extra memory.
        int start = 0;
        int cnt = 0; // Number of distinct characters
        int[] charSet = new int[256];
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++)
        {
            if (charSet[s.charAt(i)] == 0)
                cnt++;
                
            charSet[s.charAt(i)]++;

            while (cnt > 2)
            {
                // If the number of distinct characters is more than 2,
                // move start until a distinct character disapear.
                charSet[s.charAt(start)]--;
                
                if (charSet[s.charAt(start)] == 0)
                    cnt--;
                    
                start++;
            }
            
            maxLen = Math.max(i - start + 1, maxLen);
        }
        
        return maxLen; 
    }
}

No comments:

Post a Comment