AUG!!! time O(n), space O(n), beats 98% JAVA with Comment


  • 0
    //If you do not transfer string into array and use charAt() to search, space is O(1)
    //I like using array, and it does not really matter in this problem.
    public class Solution {
    
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            if(s.isEmpty())
                return 0;
            char[] sArr = s.toCharArray();
            int len = s.length();
            int first = 0;
            int second = 0;
    // Key !: use var 'latestFirst' to save the index of the latest first char when there are at least two different chars in this string. 
    // This save lots of time when you find a third different char and need to update the position
    //of the first char. 
            int latestFirst = -1;
            int maxLen = 0;
            for(int i = 1; i <= len; i++){
                if(i == len){
                    maxLen = Math.max(i - first, maxLen);
                    continue;
                }
                if(sArr[i] != sArr[i-1]){
                    if(latestFirst != -1 && sArr[i]!=sArr[latestFirst]){
                        maxLen = Math.max(i - first, maxLen);
                        first = latestFirst+1;
                    }
                    latestFirst = i-1;
                }
            }
            return maxLen;
        }
    }
    ``

Log in to reply
 

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