题目

Given a string s, find the length of the longest substring without repeating characters.

example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

我的思路

用Map存储最长子串里的元素，在重复时重置Map，直到整个string遍历结束

function lengthOfLongestSubstring(s: string): number {
    // start index and end index
    let start: number = 0,
        end: number = 0;
    // sub string max length
    let max = 0;
    // map charter to index
    let indexMap: Map<string, number> = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (indexMap.has(char)) {
            let newStartIndex: number = indexMap.get(char) as number;
            // 如果已经在map里
            // 重置窗口和map

            // 删除窗口外的元素
            removeEleFromMap(s.slice(start, newStartIndex + 1), indexMap);
            // 更新map里的startIndex
            indexMap.set(char, i);
            start = newStartIndex as number + 1;
        } else {
            // 如果不再map里
            // 加入map & 窗口长度加1
            indexMap.set(char, i);
        }
        end = i;
        // 更新max
        max = Math.max(max, end - start + 1);
    }

    // console.log(max);
    return max;


};

function removeEleFromMap<T, P>(eles: Iterable<T>, map: Map<T, P>) {
    for (const ele of eles) {
        map.delete(ele);
    }
}

// console.log(lengthOfLongestSubstring("abcabcbb"));
// console.log(lengthOfLongestSubstring("bbbbb"));
// console.log(lengthOfLongestSubstring("pwwkew"));

最优解

最优解和我的复杂度差不多，都是O(n)，空间复杂度应该是这个好点

而且代码简洁很多

function lengthOfLongestSubstring(s: string): number {
    // start index and end index
    let start: number = 0,
        end: number = 0;
    // sub string max length
    let max: number = 0;
    // store charter
    let set: Set<string> = new Set<string>();
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (set.has(char)) {
            // 如果重复 移动左指针 & 从set中移除
            let j = start;
            // 查找左指针移动到的位置
            while (s[j] !== char) {
                set.delete(s[j]);
                j++;
            }
            start = j + 1;
        } else {
            // 如果不重复 移动右指针 & 添加到set中
            set.add(s[i]);
            end = i;
        }
        max = Math.max(max, end - start + 1);
    }
    // console.log(max);
    return max;
};