AC O(n) Java Solution


  • 0
    A

    Use a map to track characters ~ indices of this char within current window.
    Once we detect the third character, we should:
    Resize window so that it contains only prev char;
    Note this can be done in O(1) instead of O(n); no need to keep moving head to right 1 at a time, we look up the last index of the char to be removed in constant time.

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int max = 0;
        Map<Character, List<Integer>> charIndices = new HashMap<>();
        int head = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            List<Integer> indices = charIndices.get(c);
            if (indices == null) { // add a new char
                if (charIndices.size() == 2) {
                    // more than 2 chars, remove 1 of the existing chars;
                    // we should adjust window so that it contains the prev char only.
                    char prev = s.charAt(i-1);
                    char remove = ' ';
                    for (Character key : charIndices.keySet()) {
                        if (key != prev) {
                            remove = key;
                            break;
                        }
                    }
                    // place new head after the last index of  the char to be removed
                    List<Integer> removeIndices = charIndices.remove(remove);
                    head = removeIndices.get(removeIndices.size() - 1) + 1;
                }
                indices = new ArrayList<Integer>();
                charIndices.put(c, indices);
            }
            indices.add(i);
            max = Math.max(max, i - head + 1);
        }
        
        return max;
    }

Log in to reply
 

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