Sunday, April 5, 2015

LeetCode 159 Longest Substring with At Most Two Distinct Characters

problem

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.

Solution

The solution is simple, but has a little bit more cases.
We maintain 3 pointer, "first", "second" and a pointer point to current position. Using a hash map, the key of it is the letter, the value is the times of appearances. And a integer record current longest length.
When the current letter is not a new letter for the hash map, just + 1 on its value in hash map.
When the current letter is new to hash map, and the size of hash map is one, put this element into hash map and set its value to 1.
When the current letter is new to hash map but it already has two elements on it, we need to
  1. compute the length once (add all value of the element in hash map together) and may need to update the result,
  2. delete the element not on the current letter's left (the letter that the first pointer pointed to) from hash map. Thinking about the string "aaabbaacccc" when current pointer point to the first "c". We need to delete "b" from hash map.
  3. update the value of the element that second pointer pointed to to (current - second). In the example above, we need to set the value of "a" in hash map from 5 to 2
  4. add new element to hash map and set its value to 1.
At the end of every loop, current letter is not equal to its left letter, set first pointer to the position second pointer point to and set second point to current position.
After the loop, we need to do a extra compute to update the longest length.
The time complexity is O(n) for one pass of the string. Space complexity is O(1) because the hash map at most has two elements.
Here is code with some comment.
public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.length() == 0) return 0;
    HashMap map = new HashMap<>(); // Character and number of its appearance
    int first = 0;
    int second = 0;
    int length = 0;
    map.put(s.charAt(0), 1);
    for (int i = 1; i < s.length(); i++) {
        
        // no new letter comes in, just update appearance times
        if (map.containsKey(s.charAt(i))) {
            map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        else {
            // new letter comes in, and just one letter in map
            // simply add the new letter and give value 1
            if (map.size() < 2) { 
                map.put(s.charAt(i), 1); // when less than two elements
            }
            else { 
                // third new element appeared
                // compute how many times the last two letters appeared. 
                int tmpLength = 0;
                for (char letter : map.keySet())
                    tmpLength += map.get(letter);
                length = Math.max(length, tmpLength);
                // delete letter not one the close left of current new letter
                map.remove(s.charAt(first));
                // update the value of the letter close to new letter. 
                map.put(s.charAt(second), i - second);
                // put new letter into map
                map.put(s.charAt(i), 1);
            }
        }
        if (s.charAt(i) != s.charAt(i-1)) {
            first = second;
            second = i;
        }
    }
    // the last two elements haven't count 
    int tmpLength = 0;
    for (char letter : map.keySet())
        tmpLength += map.get(letter);
    return Math.max(length, tmpLength);
}
Written with StackEdit.

No comments:

Post a Comment