LeetCode 3. Longest Substring Without Repeating Characters [Medium] [C++] 解題筆記

這題給定一個字串，要我們找出字元不重複的最常子串(longest substring)的長度。

EX:

        Input: "abcabcbb"

        Ans: 3 

想法:

    這題可以用一個 HashMap 來紀錄出現過得字元的位置，如果遍歷過程中某字元 a 的位置在 hashmap 中已經有

紀錄了就表示重複了，這時候長度就從 a 上一次出現的位置的下一個位置開始算起就好。另外因為 ASCII 碼只能表示

128 個字元，因此我們也可以直接宣告一個長度 128 的 array 來代替 Hashmap。

Complexity: O(n) time, O(n) space.

完整程式碼:

解法一(HashMap):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> m;
        int left = -1;
        int max_len = 0;
        for (int i = 0; i < s.size(); i++) {
            left = max(left, m[s[i]] - 1);
            m[s[i]] = i + 1;
            max_len = max(max_len, i - left);
        }
        return max_len;
    }
};

解法二(array):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // since ASCII can represent only 128 character
        vector<int> m(128, -1);   
        
        int max_len = 0;
        int start = -1;
        
        for (int i = 0; i < s.size(); i++) {
            start = max(m[s[i]], start);
            m[s[i]] = i;
            max_len = max(max_len, i - start);
        }
        
        return max_len;
    }
};