題目： LeetCode - 3. Longest Substring Without Repeating Characters

題目說明

給一個 String，找出這個 String 裡面最長的不重複子陣列。

解題思路

定義一個陣列紀錄每個英文字母最後出現的位置，使用一個迴圈，j 為子陣列的右端點，i 為子陣列的左端點，每一次 i 都更新為 max(i, v[s[j] + 1]) 這樣就可以確保子陣列中沒有重複的元素，此時子陣列的長度為 j - i + 1，最後更新 maxL 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), maxL = 0;
        vector<int> v(128, -1);
        for(int i = 0, j = 0; j < n; ++j)
        {
            i = max(i, v[s[j]] + 1);
            maxL = max(maxL, j - i + 1);
            v[s[j]] = j;
        }
        return maxL;
    }
};