JavaScript solution in O(n) time and space

  • 0

    This was a pretty fun problem!

    Basically we just do a two-pointer iteration, starting with the first and moving forward.

    Using a hashmap lets us keep track of the characters we've already encountered, for free.

    A small optimization is to check if our remaining iterable length is less than the longest we've found so far--if it is, we can just return because we know we'll never get a longer string

    var lengthOfLongestSubstringTwoDistinct = function(s) {
        let longest = 0;
        for (let i = 0; i < s.length; i++) {
            // Optimize for O(n) time to avoid O(n^2)
            if (longest > s.length - i) return longest;
            let map = new Set();
            let distinct = 1;
            let len = 1;
            for (let j = i+1; j < s.length; j++) {
                if (!map.has(s.charAt(j))) {
                    distinct += 1;
                if (distinct > 2) break;
            longest = Math.max(longest, len);
        return longest;

Log in to reply

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