字节&Leetcode3：无重复字符的最长子串

[sisterAn]

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

附leetcode：leetcode

[shengq666]

对原数组进行判断，是否在arr里 如果在就将arr字符串之前的全部去除，不在就直接push，最后判断长度

var lengthOfLongestSubstring = function(s) {
    let arr = [];
    let length = 0;
    for(let item of s){
        if(arr.includes(item)){
            let index = arr.indexOf(item);
            arr.splice(0,index+1);
        }
        arr.push(item);
        length = length > arr.length ? length : arr.length;
    }
    return length;
};

[Aiyoweioo]

快慢指针维护一个滑动窗口，如果滑动窗口里面有快指针fastp所指向的元素（记录这重复元素在滑动窗口的索引tmp），那么滑动窗口要缩小，即慢指针slowp要移动到tmp的后一个元素。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let res = 0, slowp = 0, tmp = 0
  for(let fastp = 0; fastp < s.length; fastp++) {
    tmp = s.substring(slowp,fastp).indexOf(s.charAt(fastp)) // 滑动窗口有没有重复元素
    if(tmp === -1) { // 没有
      res = Math.max(res, fastp-slowp+1) // 上一次值和滑动窗口值大小比较
    }else{ // 有，移动慢指针， 是slowp+tmp+1不是tmp+1，因为tmp是根据滑动窗口算的
      slowp = slowp + tmp + 1
    }
  }
  return res
};

细节： 快指针也要从0开始，如果从1开始，类似'aaaa'，结果就是0，因为tmp永远不等于-1

[fanefanes]

方法一：悬浮框圈出满足条件的字符串，时间复杂度O(n),空间复杂度O(n),

/**
 * @param {string} str
 * @return {number}
 */
  function lengthOfLongestSubstring(str){
          if(!str || str.length < 0) return 0;
          let num = 0;
          let strArr = str.split('');
          let lengthOfSubstring = [];
          for(let i = 0; i < strArr.length; i ++){
               const index = lengthOfSubstring.indexOf(strArr[i])
               if( index <0 ){
                     lengthOfSubstring.push(strArr[i])
               }else{
                     lengthOfSubstring = lengthOfSubstring.splice(index+1) 
                     lengthOfSubstring.push(strArr[i])
               }
               num = num<lengthOfSubstring.length?lengthOfSubstring.length:num
          }
          return num;
     }

方法二：双悬浮框从字符串首尾圈出满足条件的字符串，直到重合，时间复杂度O(n/2),空间复杂度O(n),

/**
 * @param {string} str
 * @return {number}
 */
function lengthOfLongestSubstring(str){
    if(!str || str.length < 0) return 0;
    let num = 0;
    let strArr = str.split('');
    let lengthOfStartSubstring = [];
    let lengthOfEndSubstring = [];
    let loopTime = strArr.length - 1
    for(let i = 0; i <= loopTime; i ++){
         const startIndex = lengthOfStartSubstring.indexOf(strArr[i])
         const endIndex = lengthOfEndSubstring.indexOf(strArr[loopTime-i])
         if( startIndex <0 ){
               lengthOfStartSubstring.push(strArr[i])
         }else{
               lengthOfStartSubstring = lengthOfStartSubstring.splice(startIndex+1)
               lengthOfStartSubstring.push(strArr[i])
         }
          if( endIndex <0 ){
              lengthOfEndSubstring.push(strArr[ loopTime-i])
         }else{
               lengthOfEndSubstring = lengthOfEndSubstring.splice(endIndex+1)
               lengthOfEndSubstring.push(strArr[loopTime-i])
         }
         console.log(lengthOfStartSubstring, lengthOfEndSubstring)
         let lengthOfSubstring = lengthOfStartSubstring.length>lengthOfEndSubstring.length?lengthOfStartSubstring.length:lengthOfEndSubstring.length
         num = num<lengthOfSubstring?lengthOfSubstring:num
            console.log(i)
         if(2*i - loopTime >= lengthOfStartSubstring.length) return;
    }
    return num;
}

[sisterAn]

解法一：维护数组

解题思路： 使用一个数组来维护滑动窗口

遍历字符串，判断字符是否在滑动窗口数组里

• 不在则 push 进数组
• 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
• 然后将 max 更新为当前最长子串的长度

遍历完，返回 max 即可

画图帮助理解一下：

代码实现：

var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index !== -1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length, max) 
    }
    return max
};

时间复杂度：O(n²)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)

空间复杂度：O(n)

解法二：维护下标

解题思路： 使用下标来维护滑动窗口

代码实现：

var lengthOfLongestSubstring = function(s) {
    let index = 0, max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        index = s.substring(i, j).indexOf(s[j]) 
        if(index !== -1) { 
            i = i + index + 1 
        } 
        max = Math.max(max, j - i + 1) 
    }
    return max
};

时间复杂度：O(n²)

空间复杂度：O(n)

解法三：优化的Map

解题思路：

使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标

使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标

遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中

最后，返回 max 即可

代码实现：

var lengthOfLongestSubstring = function(s) {
    let map = new Map(), max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        if(map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

[zhaojinzhao]

function getMaxLen(str) {
var maxLen = 0, startIndex = 0;
for(var i = 0; i < str.length; i++) {
for(var j = startIndex; j < i; j++) {
if (str[j] === str[i]){
startIndex = j + 1;
break
}
}
maxLen = Math.max(maxLen, i - startIndex + 1);
}
return maxLen;
}

[fengmiaosen]

经典的滑动窗口算法题

var lengthOfLongestSubstring = function (s) {

    if (s.length < 2) {
        return s.length;
    }

    let window = new Map();

    let left = 0;
    let right = 0;

    let res = 0;

    while (right < s.length) {
        let rc = s[right];
        right++;

        if (window.has(rc)) {
            window.set(rc, window.get(rc) + 1);
        } else {
            window.set(rc, 1);
        }

        while (window.get(rc) > 1) {
            let lc = s[left];
            left++;

            if (window.has(lc)) {
                window.set(lc, window.get(lc) - 1);
            }
        }

        res = Math.max(res, right - left);
    }

    return res;
};

[lovetingyuan]

var lengthOfLongestSubstring = function(s) {
  let max = 0
  let map = {}
  let start = 0
  let end
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] >= 0) {
      start = map[s[i]] + 1
    }
    map[s[i]] = i
    end = i
    Object.keys(map).forEach(c => {
      if (map[c] < start) {
        map[c] = -1
      }
    })
    if (max < (end - start + 1)) {
      max = end - start + 1
    }
  }
  return max
};

[U-LAN]

代码中的 res 变量存储的是所有不重复子串及其长度，就本题目完全可以不需要这个变量，如果题目需要返回不重复子串则可以用到

var  lengthOfLongestSubstring  =  function (str) {
  if (!str) return 0

  let res = {} // 存储所有不重复子串
  let max = 0  
  let s = ''

  for (const char of str) {
    let idx = s.indexOf(char)
    s += char

    if (idx === -1) {    // 不重复

      res[s] = s.length   // 存储不重复子串
      max = Math.max(max, s.length)

    } else {     // 重复，从重复的字符的第一个个位置进行分割

      let del = s.slice(0, idx + 1)
      res[del] = del.length  // 存储不重复子串
      max = Math.max(max, del.length)

      s = s.slice(idx + 1)
      res[s] = s.length  // 存储不重复子串
      max = Math.max(max, s.length)
    }
  }
  res[s] = s.length
  max = Math.max(max, s.length)

  return max
}

[limeng01]

悬浮窗

var lengthOfLongestSubstring = function (s) {
        let next = 0;
	let start = 0;
	let arr = [];
	let len = 0;
	while (true) {
		if (arr.includes(s[next])) {
			arr = [];
			start++;
			next = start;
			if (start === s.length - 1) {
				return len;
				break;
			}
		} else {
			if (s[next]) {
				arr.push(s[next]);
				next++;
			} else {
				return len;
				break;
			}
		}
		len = arr.length > len ? arr.length : len;
	}
};

[JohnApache]

利用了 Map 存储已经存放的char

const lengthOfLongestSubstring = (source: string) => {
    if (source.length <= 1) return source.length;
    let i = 0;
    let map: Record<string, boolean> = {};
    let count = 0;
    let maxCount = 0;
    while (i < source.length) {
        const char = source.charAt(i);
        if (!map[char]) {
            count++;
            map[char] = true;
            i++;
            continue;
        }
        if (maxCount < count) {
            maxCount = count;
        }
        map = {}; count = 0;
    }
    return maxCount;
};