# 3 - Longest Substring Without Repeating Characters

解法一 - Brute Force

我先用一種 naive 的做法，每一種 substr 都去看看這個 substr 裡是不是全部 char 都 unique，如果是的話，再跟 maxLen 比比看長度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0; // if use INT_MIN, mySet.size() > maxLen == 0...

        set<char> mySet; 
        for(int s1=0; s1<s.length(); s1++) {
            mySet.clear();
            mySet.insert(s[s1]);

            for(int s2=s1+1; s2<s.length(); s2++) {
                if(mySet.find(s[s2]) != mySet.end())
                    break;
                mySet.insert(s[s2]);
            }
            maxLen = max(maxLen, (int)mySet.size());
        }

        return maxLen;
    }
};

// idea: use two pointer to slide through each substring and calculate length

實作起來的效率非常差：

Runtime: 1040 ms, faster than 5.04% of C++ online submissions for Longest Substring Without Repeating Characters. Memory Usage: 266.2 MB, less than 5.01% of C++ online submissions for Longest Substring Without Repeating Characters.

解法二 - Sliding Window

Sliding window 主要的概念就是，如果目前的 window 還沒有重複的字母，那就移動右邊的邊界(在下面的實作中由 j 表示)，如果有重複的字母，那就移動左邊的邊界(由 i 表示)直到沒有

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.length();
        set<char> st;
        int ans=0, i=0, j=0;

        while(i<n && j<n) {
            if(st.find(s[j]) == st.end()) {
                st.insert(s[j]);
                j++;
                ans = max(ans, j-i);
            }
            else
            {
                st.erase(st.find(s[i]));
                i++;
            }
        }

        return ans;
    }
};

// idea: use two pointer to create a sliding window, if the newest char pointed by j is already in the set, then move i to the right until char pointed by j is not in the set

效率確實也比暴力解好上不少：

Runtime: 36 ms, faster than 31.63% of C++ online submissions for Longest Substring Without Repeating Characters. Memory Usage: 15.7 MB, less than 20.17% of C++ online submissions for Longest Substring Without Repeating Characters.