Fast Java O(n) solution without hashtable


  • 0
    R

    O(n) time. Only use several variables (array with length 2). Only 10ms run time.

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null) return 0;
        if (s.length() < 3) return s.length();
                
        int i = 1, j = 0, max = 0;
    
        while (i < s.length() && s.charAt(0) == s.charAt(i)) {i++;}
        
        if (i == s.length()) return i;
        char[] last = {s.charAt(0), s.charAt(i)};
        int[] index = {0, i};
        char past = last[1];
        for (; i < s.length(); i++) {
            char now = s.charAt(i);
            if (now == last[0]) {
                if (now != past) index[0] = i;
            } else if (now == last[1]) {
                if (now != past) index[1] = i;
            } else {
                max = Math.max(max, i - j);
                int rep = index[0] < index[1] ? 0 : 1;
                last[rep] = now;
                index[rep] = i;
                j = index[1-rep];
            }
            past = now;
        }
        max = Math.max(max, i - j);
        return max;
    }

Log in to reply
 

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