Longest substring without repeated character

int lengthOfLongestSubstring(string s) { deque<char> sub; deque<char>::iterator flag; int start = 0, end = 0; int max = 0; for (int i = 0; i < s.length(); i++) { if ((flag = find(sub.begin(), sub.end(), s[i])) != sub.end()) { while (true) { if (sub.begin() == flag) { sub.pop_front(); break; } sub.pop_front(); } } sub.push_back(s[i]); if (max < sub.size()) max = sub.size(); } return max; }

주어진 문자열 안에서 문자 중복 없는 가장 긴 substring을 구한다.

deque를 사용하여 sliding window 방식으로 구현

새로운 문자를 읽을 때마다 push_back, push할 때마다 max값 갱신

문자열 탐색 도중 이미 있는 문자가 발견되면 중복되는 문자 이전 문자들을 모두 pop_front