LeetCode Js-3. Longest Substring Without Repeating Characters

    AllenLi
    LeetCode Js-StringResult

    Given a string s, find the length of the longest substring without repeating characters.
    ex. A substring is a contiguous non-empty sequence of characters within a string.

    給與一個字串 s，找出最長且不重複字元的子字串長度。

    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.

    solution:
    1. 定義 charSet 是一個 Set() 集合，left 為 0，maxLength 為 0。
    2. 運用 for 迴圈搭配 while 建立 sliding window。
    3. 依序向右遍歷字串，當發現重複字串時，則 left 向右移動直到移除重複字串。
    4. 每次窗口大小變動時，更新 maxLength。

    Code 1: BigO(n) Sliding Window

    function lengthOfLongestSubstring(s: string): number {
    let charSet: Set<string> = new Set();
    let left: number = 0, maxLength: number = 0;  

    for (let right = 0; right < s.length; right++) {
        while(charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
};

    Related Posts