LeetCode.3 - 无重复字符的最长子串

• LeetCode - 3. 无重复字符的最长子串

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

思路

1. 遍历所有以下标 i (0 <= i < s.length) 为结束字符的最长子串长度，从中得到目标结果
2. 使用滑动窗口的思路，维护 leftIndex 和 rightIndex（实际上，遍历时的下标 i 即 rightIndex）
3. 维护 marked 字典，记录字符 char 在遍历过程中所在的最大下标
4. 遍历时，对于下标 i，char = s[i]，若 marked[char] 存在且 marked[char] >= leftIndex 则令 leftIndex = marked[char] + 1
5. 时间复杂度 O(n)

var lengthOfLongestSubstring = function (s) {
  let leftIndex = 0
  let result = 0
  const marked = {}
  for (let i = 0; i < s.length; ++i) {
    const char = s[i]
    if (marked[char] !== undefined && marked[char] >= leftIndex) {
      leftIndex = marked[char] + 1
    }
    marked[char] = i
    result = Math.max(result, i - leftIndex + 1)
  }
  return result
}