3. Longest Substring Without Repeating Characters (opens new window)

Description

Difficulty: Medium

Related Topics: Hash Table (opens new window), String (opens new window), Sliding Window (opens new window)

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

Example 1:

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

Example 2:

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

Example 3:

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.

Constraints:

• 0 <= s.length <= 5 * 10⁴
• s consists of English letters, digits, symbols and spaces.

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 方法一：暴力求解
 逐个生成子字符串
 看它是否不含有重复的字符
 
 方法二：滑动窗口及优化
 关键字：重复字符 -> 出现1次
 模式识别1:一旦涉及出现次数，需要用到散列表
 构造子串，散列表下标
 模式识别2:涉及子串，考虑滑动窗口
 
 举例分析思路
 p w w k e w
 
 测试：
 字符串为空的情况
 字符串均为重复字符的情况
 测试其他常规输入
 
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set();
    let [start, end, maxLen] = [0, 0, 0];
    
    while(end < s.length) {
        set.has(s[end]) ? set.delete(s[start++]) : set.add(s[end++]);
        
        maxLen = Math.max(maxLen, set.size);
    }
    
    return maxLen;
};