Java O(n) solution, beats 94%


  • 0
    public class Solution {
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            if(s == null) {
                return 0;
            } else if(s.length() <= 2){
                return s.length();
            }
            
            char[] arr = s.toCharArray();
            char[] chars = new char[2];
            int[]  idxFirst = new int[2];
            int[]  idxLast = new int[2];
            chars[0] = arr[0];
            int cnt = 1;
            int lastIdx = 0;
            int result = Integer.MIN_VALUE;
            for(int i = 1; i < arr.length; i++){
                if(arr[i] == chars[0] || arr[i] == chars[1]){
                    int idx = arr[i] == chars[0] ? 0 : 1;
                    idxLast[idx]=i;
                    cnt++;
                } else {
                    int idx = arr[i - 1] == chars[0] ? 1 : 0;
                    if(chars[idx] == 0){
                        cnt++;
                        chars[idx] = arr[i];
                        idxFirst[idx] = idxLast[idx] = i;
                    } else {
                        chars[idx] = arr[i];
                        idxFirst[1 - idx] = idxLast[idx] + 1;
                        idxFirst[idx] = idxLast[idx] = i;
                        cnt = idxLast[idx] - idxFirst[1-idx] + 1;
                    }
                }
                result = Math.max(result, cnt);
            }
            return result;
        }
    }
    

Log in to reply
 

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