3. Longest Substring Without Repeating Characters

下記を見てsetを使う方法とsliding windowを使う方法を学んだ。

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1275071/C%2B%2B-oror-100-faster-Simple-approach-with-two-methods

set

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.length();
        if(n==0){
            return 0;
        }            
        
        set<char> st;
        int maxSize=0;
        int i=0;
        int j=0;
        while(j < n)
        {
//stに今の文字がなければ、今までの最大値と今のsetのサイズを比較
            if(st.count(s[j])==0){
                st.insert(s[j]);
                maxSize = max(maxSize, (int)st.size());
                j++;
            }
            else{
                st.erase(s[i]);
                i++;
            }
        }
        return maxSize;        
    }
};

sliding window

256は1byteだから256文字文ってことのようだ。文字そのものではなく、asciiの数値で扱う発想はなかった。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> vec(256, -1);
        int maxSize=0;
        int i=0;
        int j=0;
        int n=s.size();
        
        while(j<n){
//文字をasciiの数値として扱っている。
            if(vec[s[j]] != -1)
            {
                i = max(vec[s[j]]+1, i);
            }
            vec[s[j]] = j;

            maxSize = max(maxSize, j-i+1);

            j++;                 
        }
        return maxSize;
    }
};