Java O(n) solution by storing the index of last appearance of each distinct character


  • 0
    T

    We have two pointers:i,j point the head and tail of the window which is a substring with at most two distinct characters. Then use an array to store the last appearance index of two distinct characters in the window. j keep move forward, when the third distinct character come in, we want to remove the character that disappears earlier in the window rather than the one disappears later. By checking the array, we remove the first character that disappears earlier and setting the window head: i = last appearance index of the removing character +1. continue the steps until j meets the end of s.

    public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int result = 0;
        if(s == null || s.length() == 0) return 0;
        
        char[] array = s.toCharArray();
        List<Integer> dq = new ArrayList<Integer>();
        dq.add(0);
        int i =0, j=1;
        for(; j<s.length(); j++) {
            char c = array[j];
            if(array[dq.get(0)] == c) {
                dq.remove(0);
            } else if(dq.size() == 2 && array[dq.get(1)] == c) {
                dq.remove(1);
            } else if(dq.size() == 2){//this character is the third distinct characters
                result = Math.max(result, j-i);
                i = dq.remove(0)+1;//remove the first distinct character and i set to the next index after the last appearance of this character
            }
            dq.add(j);//insert the last appearance of the character in order
            
        }
        return Math.max(result, j-i);
    }
    }

Log in to reply
 

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