# 3-Longest Substring Without Repeating Characters
###### tags: `Medium`、`Sliding_window`

## Question:
https://leetcode.com/problems/longest-substring-without-repeating-characters/

## Key:
- 直觀想法(Brute force):先建一個list收集出現過的字母，如果遇到重複的就去除，但要記得保留沒重複的部分，並且計算一次長度

- Sliding window:用一個 set 來儲存目前 window 裡面有的 char，然後每次都要確定 window 裡已經沒有重複的 char，才會繼續擴張 window，先確定 windowEnd 的 char 不在 substring 中。假如最後面的指標所指的值在sliding window中已經出現過，就將最前面的指標移動到該值在sliding window 中的位址，並將set中的char刪除，否則最後面的指標就一直前進，並記錄和更新最大長度，直到字串尾巴。

## Sliding window Solution
### C++ version

class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    int n = s.length();
    set<char> st;
    int maxLen = 0, windowStart = 0, windowEnd = 0;

    while(windowEnd < n) {
      if(st.find(s[windowEnd]) == st.end())//if we don't find the char, we insert it to the set
      {
        st.insert(s[windowEnd]);
        maxLen = max(maxLen, windowEnd-windowStart+1);
        windowEnd++;
      }
      else {
        st.erase(st.find(s[windowStart]));
        windowStart++;
      }
    }

    return maxLen;
  }
};

### Python version

class Solution(object):
    def lengthOfLongestSubstring(seld, s):
        """
        :type s: str
        :rtype: int
        """
        if 5*10**4 > len(s) > 0:
            alphas = []
            cnts = []
            cnt = 0
            for i in range(len(s)):
                if s[i] not in alphas:
                    alphas.append(s[i])
                    if i == len(s)-1:
                        cnt = len(alphas)
                        cnts.append(cnt)
                else:
                    cnt = len(alphas)
                    cnts.append(cnt)
                    for a in range(len(alphas)):
                        if alphas[a] == s[i]:
                            alphas.append(s[i])
                            alphas = alphas[a+1:]
                            break
            if len(cnts) == 0:
                return 0
            else:
                return max(cnts)
        else:
            return 0
                

- 大神想法:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        answer = ''
        result = 0
        for i in s:
            if i not in answer:
                answer += i
            else:
                if len(answer) > result:
                    result = len(answer)
                answer = answer[1:] 
                while i in answer:
                    answer = answer[1:]
                answer += i
        if len(answer) > result:
            result = len(answer)
        return result