0003._longest_substring_without_repeating_characters.md

Links:

1. https://leetcode.com/problems/longest-substring-without-repeating-characters/
2. https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

Tags

1. 字符串
2. 双指针（滑动窗口）
3. 哈希表（dict或者set，去重）

Solution1:

1. hash_table记录反向索引，{value:index}。用来判断字符是否出现过。
2. 滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界。每次移动需要计算当前长度，并判断是否需要更新最大长度。

Python

class Solution:
    def lengthOfLongestSubstring(self, s): 
        if not s:
            return 0

        res, start, n = 0, 0, len(s)
        cache = {}

        for right in range(n):
            start = max(start, cache.get(s[right], -1) + 1)
            res = max(res, right - start + 1)
            cache[s[right]] = right 
            
        return res

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        start, max_length, cache = 0, 0, {}

        for i, num in enumerate(s):
            if num in cache and start <= cache[num]:
                start = cache[num] + 1
            else:
                max_length = max(max_length, i - start + 1)

            cache[num] = i

        return max_length

---

Go

package main

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func lengthOfLongestSubstring(s string) int {
	ans, left, m := 0, 0, make(map[rune]int)
	for right, v := range s {
		if _, ok := m[v]; ok {
				left = max(left, m[v] + 1)
		}

		m[v] = right
		ans = max(ans, right-left+1)
	}
	return ans
}