3. Longest Substring Without Repeating Characters

Loading...LeetCode

better

Time: O(n)

space: O(1), number of unique characters limited

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {

    if (s.length < 2) return s.length;
    
    const memo = {};
    
    let max = 0;
    let left = 0;
    for (let i = 0; i < s.length; i++) {
        curr = s.charAt(i);
        if (memo[curr] !== undefined) {
            left = Math.max(memo[curr] + 1, left);
        }
        max = Math.max(max, i - left + 1);
        memo[curr] = i;
    }

    return max;
};

Brute force

time: O(n^2)

time: O(n)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    s = [...s];
    // empty? length 1?
    if (s.length < 2) return s.length;
    
    let max = 0;
    for (let i = 0; i < s.length; i++) {
        const set = new Set([s[i]]);
        for (let j = i + 1; j < s.length; j++) {
            const curr = s[j];
            if (set.has(curr)) {
                break;
            } else {
                set.add(curr);
            }
        }
        max = Math.max(max, set.size);
    }

    return max;
};