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

题目

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

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

示例 1:

输入: s = "abcabcbb"

输出: 3

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

示例 2:

输入: s = "bbbbb"

输出: 1

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

示例 3:

输入: s = "pwwkew"

输出: 3

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

提示：

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

解题思路1

通过滑动窗口方式解题。维护一个滑动窗口，滑动窗口左右边界分别为l和r，再用一个map来存储字符和其在窗口内的个数。

滑动过程中，当移动l时，则把移出窗口左边界的字符从map中删掉；移动右窗口时，则只要下一个字符没有超出字符串而且下一个字符在窗口中出现的个数为0，则一直右移。

完成一轮左右边界的移动后，r-l+1即为当前的最长子串的极大值。

实现代码1

func lengthOfLongestSubstring(s string) int {
	m := map[byte]int{}
	l := 0
	r := -1
	ans := 0
	for l < len(s) {
		if l != 0 {
			delete(m, s[l-1])
		}

		for r+1 < len(s) && m[s[r+1]] == 0 {
			m[s[r+1]]++
			r++
		}

		ans = max(ans, r-l+1)
		l++
	}

	return ans
}

func max(m, n int) int {
	if m > n {
		return m
	}

	return n
}

解题思路2

通过l和r维护一个滑动窗口，用一个map记录字符所对应的当前访问过的最大的下标。

对r进行移动，如果当前字符出现过，那么尝试把l移动到当前字符上一次出现的位置的下一个字符（前提是不能出现l左移的情况）。

每移动一次后的极大值为r-l+1

实现代码2

func lengthOfLongestSubstring(s string) int {
	m := map[byte]int{}
	l := 0
	r := 0
	ans := 0
	for r < len(s) {
		//检查字符是否出现过且在当前窗口内
		if lastPos, ok := m[s[r]]; ok && lastPos >= l {
			l = max(l, lastPos+1)
		}

		m[s[r]] = r
		ans = max(ans, r-l+1)
		r++
	}

	return ans
}

解题思路3（20026.1.15）

滑动窗口 + map计数，滑动窗口维护一个没有重复字符的窗口，如果遇到了重复字符，则不断往右边移动left

解题思路3

func lengthOfLongestSubstring(s string) int {
	m := make(map[uint8]int)
	left, right := 0, 0
	ans := 0
	for right < len(s) {
		ch := s[right]
		m[ch]++
		for m[ch] > 1 {
			m[s[left]]--
			left++
		}

		ans = max(ans, right-left+1)
		right++
	}

	return ans
}

源码：https://github.com/xzygis/algorithm/tree/master/leetcode