[LeetCode 解題紀錄] 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

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

Problem:

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 * 104
• s consists of English letters, digits, symbols and spaces.

題意

這題的題意很明確，就是要找出最大不重複的子字串長度。

問題解析：

通常看到找子字串、或是找到子字串長度，有蠻高機率都是使用 sliding window / two pointers 的方法來解題，透過每回合紀錄當下最大值，來找到最佳解。

解法

暴力法

一樣可以先來看看最直覺的暴力法，暴力法要遍歷所有可能的子字串，檢查每個子字串是否包含重複字元，並記錄最大長度。這種方法的時間複雜度是 O(n³)，因為需要三層迴圈：

1. 外層兩層迴圈生成所有可能的子字串。
2. 內層迴圈檢查每個子字符串是否包含重複字元。

var lengthOfLongestSubstring = function(s) {
    let max = 0;
    
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            let subStr = s.slice(i, j);
            if (isUnique(subStr)) {
                max = Math.max(max, subStr.length);
            }
        }
    }
    
    return max;
};

function isUnique(str) {
    let set = new Set();
    for (let char of str) {
        if (set.has(char)) {
            return false;
        }
        set.add(char);
    }
    return true;
}

• 時間複雜度: O(n^3)
• 空間複雜度: O(n)

Dynamic programming 動態規劃

這題也可以使用 DP 的方式來解，從剛剛的暴力法的想法出發，我們把每個位置處的最長不含重複字元的子字串記錄下來，利用查表發方式來降低重複的計算。

Dynamic programming 概念複習：

演算法筆記系列 — Dynamic programming 動態規劃

var lengthOfLongestSubstring = function(s) {
    let n = s.length;
    if (n == 0) return 0;

    let max = 1;
    let dp = new Array(n).fill(1);
    
    for (let i = 1; i < n; i++) {
        let j = i - 1;
        while (j >= 0 && s[i] !== s[j]) {
            j--;
        }
        dp[i] = (j === -1) ? dp[i - 1] + 1 : i - j;
        max = Math.max(max, dp[i]);
    }

    return max;
};

• 時間複雜度: O(n^2)
• 空間複雜度: O(n)

Sliding Window / Two Pointers

這題要找到最大(某條件下)子字串長度，最適合的還是使用 Sliding Window / Two Pointers 的解法，才會是最有效率的了。

Sliding Window / Two Pointers 概念複習：

演算法筆記系列 — Two Pointer 與Sliding Window

1. 使用兩個指針表示窗口的左邊界和右邊界，初始值都為 0。
2. 右指針向右移動，擴展窗口，直到遇到重複字元為止。
3. 當遇到重複字元時，左指針向右移動，收縮窗口，直到窗口內不再有重複字元。
4. 在每次移動窗口時，記錄窗口的大小，並更新最大窗口大小。
5. 重複步驟 2 和 3，直到右指針遍歷完整個字元串。
6. 返回最大窗口大小作為結果。

而使用這種方法，還會有著你使用什麼來紀錄子字串的差異，我們可以使用一個字串 subStr 來記錄，也可以使用一個 Hash Set 來增加查找的速度。

使用字串作為紀錄：

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let max = 0;
    let subStr = '';

    for (let right = 0; right < s.length; right++) {
        let index = subStr.indexOf(s[right]);
        if (index === -1) {
            subStr += s[right];
        } else {
            left = left + index + 1;
            subStr = s.substring(left, right + 1);
        }
        max = Math.max(max, subStr.length);
    }

    return max;
};

使用 Hash Set 作為紀錄：

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let max = 0;
    let charSet = new Set();

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

    return max;
};

不過這兩個有什麼差異呢？這個會跟實作上的細節比較相關一點，因為使用 .indexOf 在查找的時候其實還是去做遍歷整個字串，所以最差情況也是會用到 O(n) 的時間。然而使用 Hash Set 的方式，就可以讓查找時間時間降低到 O(1) (這裡只有指的是去看這個字元有沒有在子字串中的查找時間)。

兩種方法的空間複雜度都是 O(n)，因為它們都需要存儲當前窗口的字元，因此在選擇寫法上，使用 Hash Set 來作為儲存子字串，再搭配 Sliding Window 的方式會是比較好的選擇。

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記