JavaScript solution in O(n) time and space


  • 0
    W

    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;
            map.add(s.charAt(i));
            for (let j = i+1; j < s.length; j++) {
                if (!map.has(s.charAt(j))) {
                    distinct += 1;
                }
                if (distinct > 2) break;
                map.add(s.charAt(j));
                len++;
            }
            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.