O(n) time and O(1) space solution without using HashMap


  • 8
    I

    The basic idea is to store the two characters and keep track of last indices of them. When third character comes, we set the start_point to 1 + smaller index, in that way we can always throw away one character. And the length is given by current_index - start_point.

    public class Solution {
            public int lengthOfLongestSubstringTwoDistinct(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            char charOne = s.charAt(0);
            int charOneIndex = 0;
            while(charOneIndex+1 < s.length() && s.charAt(charOneIndex+1) == charOne){ // in case of "aaa"
                charOneIndex++;
            }
            if(charOneIndex == s.length()-1){
                return s.length();
            }
            char charTwo = s.charAt(charOneIndex+1);
            int charTwoIndex = charOneIndex+1;
            int startIndex = 0;
            int maxLen = charTwoIndex+1;
            for(int i=charTwoIndex+1; i<s.length(); i++){
                char c = s.charAt(i);
                if(c != charOne && c != charTwo){ //new character comes, update index and char
                    startIndex = Math.min(charOneIndex, charTwoIndex)+1;
                    charOneIndex = Math.max(charOneIndex, charTwoIndex);
                    charOne = charOneIndex == charTwoIndex ? charTwo : charOne;
                    charTwoIndex = i;
                    charTwo = c;
                }
                else{ //same character comes, update max length
                    if(c == charOne){
                        charOneIndex = i;
                    }
                    else{
                        charTwoIndex = i;
                    }
                    if(i - startIndex + 1 > maxLen){
                        maxLen = i - startIndex + 1;
                    }
                }
            }
            return maxLen;
        }
    }

Log in to reply
 

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