3. Longest Substring Without Repeating Characters
下記を見てsetを使う方法とsliding windowを使う方法を学んだ。
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; } };