[leetcode - Bliend-75 ]3. Longest Substring Without Repeatin

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 的迴圈并清除 seti = 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)