###### tags: `LeetCode` `Substring`

# 0003. Longest Substring Without Repeating Characters (Medium)
耗時：13 分鐘

## 題目
Given a string s, find the length of the longest substring without repeating characters.

## 思路
1. 從起點`i`開始，利用`set`依序搜尋是否有重複元素，若有，則認為找到一段子字串，紀錄長度並確認是否為最長子字串。 (沒利用到過往資訊)
* Time Complexity：O(n^2)
* Space Complexity：O(n)

2. <參考別人的解法> 利用`queue`與`set or unordered_set`紀錄過往資訊，這樣只需遍歷一次整個字串，便可以得出結果，以下舉例
(1) `s: pwwkew, queue: empty, set: empty`
(2) 將p放入queue與set，`s: wwkew, queue: p, set: p`
(3) 將w放入queue與set，`s: wkew, queue: p->w, set: p, w`
(4) 檢查到w於set內，則紀錄當下queue的長度(`2`)，清空set，並只保留重複字元後以後的子字串
`s: kew, old_queue: q(pop)->w(pop)->w, queue: w, set: w`
(5) 以此類推，直到遍歷整個字串

* Time Complexity：O(n)
* Space Complexity：O(n)

### 程式碼

#include <set>

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> sub_str;
        int longest = 0;
        int _len = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            _len = 0;
            sub_str.clear();
            
            for (int j = i; j < s.length(); ++j) {
                if (sub_str.count(s[j])) {
                    _len = j - i;
                    
                    if (_len > longest) { longest = _len; }
                    
                    break;
                }
                else if (j == s.length() - 1) {
                    _len = j - i + 1;
                    
                    if (_len > longest) { longest = _len; }
                    
                    break;
                }
                
                else { sub_str.insert(s[j]); }
            }
        }
        
        return longest;
    }
};

後續改良 (不計時)

#include <unordered_set>
#include <queue>

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> sub_set;
        queue<char> sub_queue;
        int longest_len = 0;
        int _len = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            if (sub_set.find(s[i]) != sub_set.end()) {
                _len = sub_queue.size();
                longest_len = (_len > longest_len) ? _len : longest_len;
                
                while (sub_queue.front() != s[i] && !sub_queue.empty()) {
                    sub_set.erase(sub_queue.front());
                    sub_queue.pop();
                }
                cout << sub_queue.front();
                sub_queue.pop();
            }
            
            sub_queue.push(s[i]);
            sub_set.insert(s[i]);
        }
        
        _len = sub_queue.size();
        longest_len = (_len > longest_len) ? _len : longest_len;
        
        return longest_len;
    }
};