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

給定一個 string 找到該字串中沒有重複的 sub-string 的最長長度。

Example :

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Coding 1 - double for loop and set O(n^2)

var lengthOfLongestSubstring = function(s) {
  if (s.length === 0) return 0;

  let max = 1;
  for (let i = 0; i < s.length - 1; i++) {
    const set = new Set();
    set.add(s[i])
    for (let j = i + 1; j < s.length; j++) {
      if (set.has(arr[j])) {
        break;
      }
      set.add(arr[j]);
    }
    max = Math.max(max, set.size);
  }
  return max;
};

• i = 0 -> pwwkew, set 是空的所以將 p 放入
• i = 0, j = 1 -> pwwkew，set = {'p'}，j 指到的 w 不存在於 set 中故將 w 放入
• i = 0, j = 2 -> pwwkew, set = {'p', 'w'}, j指到的 w 已存在於 set 中，結束 j 的迴圈並清除 set
• i = 1 -> pwwkew, set 是空的所以將 w 放入
• i = 0, j = 2 -> pwwkew, set = {'w'}, j指到的 w 已存在於 set 中，結束 j 的迴圈並清除 set

以此類推找到不重複的字元的最大長度即可

• Time complexity: O(n^2)

Coding 2 - two point and set O(n)

var lengthOfLongestSubstring = function(s) {
  let max = 0, start = 0, current = 0;
  const set = new Set();
  while (current < s.length) {
    if (set.has(s[current])) {
      set.delete(s[start]);
      start++;
    } else {
      set.add(s[current]);
      current++;
      max = Math.max(max, set.size);
    }
  }
  return max;
};

current 用來紀錄遍歷到 s 的第幾個 chart，而 start 用來記錄目前 current 指針走的的 index 之前不重複的 sub-string 的起始點，如果遇到 current 遇到重複的 chart（存在於 set 中）時，start 往 current 的位置走並清除掉之前設定進 set 中的值，當 start 與 current 重合時，代表從 current 這個點開始重新跑。

• Time complexity: O(n)