Java Sliding window method, O(n) time with clear comment to follow


  • 0
    public class Solution {
        /*
         Idea: sliding window
               * Maintain a window containing at most 2 distinct letters. 
               1) Keep expanding its right boundary until reaching the end or adding one more letter will break this rule. 
               2) Then update the "result" using the current window's size. 
               3) Then update left boundary of the window to make window contains 2 distinct letters. 
               
               Key : The quicker you update the left boundary, the faster your algorithm will be. 
               
         Method : Two pointers (using left and right)
         1) Initialize left = right = 0;
         2) When increasing the right boundary, maintaining 2 "letters" and 2 "indexes" to keep tracking of the two distinct
            letters within the current window and the indexes of their last appearence. 
         3) When adding one more letter will give 3 distinct letters in the window, update result to max(result, right - left);
         4) update left to min(index1, index2) + 1; Keep doing 1 2 3 and 4 until reaching the end
         
         Performance: 
                Time O(n) Space O(1)
                real time: 6 ms
         Extension: if 2 becomes k
                    Using hashSet to store distinct letters and TreeMap to store the (index, letter) pairs. 
                    When set's size becomes k + 1, update left to map.firstKey() + 1 and delete corresponding contents. 
         */
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            if (s.length() < 3) {
                return s.length();
            }
            int index1 = -1;
            int index2 = -1;
            int cnt = 0;
            char a = 'a';
            char b = 'a';
            int left = 0;
            int right = 0;
            int result = 0;
            while (right < s.length()) {
                char curr = s.charAt(right);
                if (index1 == -1 || a == curr) {
                    index1 = right;
                    a = curr;
                } else {
                    if (index2 == -1 || b == curr) {
                        index2 = right;
                        b = curr;
                    } else {
                        result = Math.max(result, right - left);
                        if (index1 > index2) {
                            left = index2 + 1;
                            index2 = right;
                            b = curr;
                        } else {
                            left = index1 + 1;
                            index1 = right;
                            a = curr;
                        }
                    }
                }
                right ++;
            }
            return Math.max(result, right - left);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.