3. Longest Substring Without Repeating Characters

Leetcode

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

題目

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.

解答

• 方法一 - Sliding window

題目需要求的是最長的子字串，並且子字串中的字母都不重複，所以思考方向很簡單，由左往右遍歷當新添加進來的字母並不在子字串中的話就代表可以繼續，但如果有遇到重複的字母時，就需要將子字串中之前遇到的同個字母從左邊開始一直移除

範例："abcabcbb"

遍歷到第三個元素(c)時：

子字串會是 "abc"

接著遍歷到第四個元素(a)時：

發現已經跟子字串中的第一個元素重複了，所以需要將第一個元素刪除，因此此時的子字串會變為 "bca"

遍歷到第五個元素(b)時：

發現也跟子字串中的第一個元素重複了，刪除第一個元素，此時子字串為 "cab"

......

......

這樣依序遍歷下去，每一輪中也順便統計最長的子字串長度後，就可以求得解答了

var lengthOfLongestSubstring = function(s) {
    const arr = [];
    let max = 0;

    for (let i=0; i<s.length; i++) {
        const value = s[i];
        while(arr.includes(value)) {
            arr.shift();
        }
        arr.push(value);
        max = Math.max(max, arr.length);
    }

    return max;
};

Runtime: 80 ms Beats 67.85% of users with JavaScript

Memory: 53.52 MB Beats 47.06% of users with JavaScript

參考資料

滑動視窗(Sliding Window) - HackMDHackMD

延伸題目

424. Longest Repeating Character Replacement