3

Posted on In , Views:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(256, -1); // record the last seen position for each character
        // 原本用map寫但卡測資，因為map預設所有東西都是0，而我們要設定的值是-1
        // 如果要用map寫，在修改l的時候需要先判斷資料是否存在(last.find(curr))
        char curr;
        int ans = 0;
        for(int l=0, r=0; r<s.length(); ++r){
            curr = s[r];
            l = max(l, last[curr]+1);
            ans = max(ans, r-l+1);
            last[curr] = r;
        }
        return ans;
    }
};