无重复字符的最长子串

题目

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

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

示例 1:

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

示例 2:

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

示例 3:

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

Go 语言实现

滑动窗口方案

所谓滑动窗口,就是一个可以移动和改变长度的 list,本实现中就是引用了该方案。是典型的动态规划策略实现。

思路:利用字符串的切片功能,完成该窗口的管理,仅仅需要记录该窗口的起始索引即可,所看到的内容,就是从该起始位置开始之后连续的多个不重复字符,如下表所示:

步骤 测试字符串 窗口
0 ababcddcba ababcddcba
1 ababcddcba ababcddcba
2 ababcddcba ababcddcba
3 ababcddcba ababcddcba
4 ababcddcba ababcddcba
5 ababcddcba ababcddcba
6 ababcddcba ababcddcba
7 ababcddcba ababcddcba
8 ababcddcba ababcddcba
9 ababcddcba ababcddcba

上表中,窗口列加粗加下划线显示的部分就是窗口。大家可以看到,是一个向右逐步滑动和动态改变大小的容器。我们其实仅仅需要记录起始位置即可,因为结束的位置和我们当前遍历字符串内字符的位置是一致的。

编程实现,下面的程序在 LeetCode 上测试通过,表现为:

执行用时 : 0 ms , 在所有 golang 提交中击败了 100 % 的用户。

内存消耗 : 2.6 MB , 在所有 golang 提交中击败了 97.01% 的用户。

func lengthOfLongestSubstring(s string) int {
	// 当前最大长度
	maxLen := 0
	// 起始 索引
	beginIdx := 0
	// 遍历全部的字符
	for i, l := 0, len(s); i < l; i++ {
		// 通过切片获取一个窗口,该窗口记录了当前不重复的字符串
		idx := strings.Index(s[beginIdx:i], string(s[i]))

		if idx == -1 {
			// 不重复字符
			// 统计最大长度
			if maxLen < i - beginIdx + 1 {
				maxLen = i -beginIdx + 1
			}
		} else {
			// 重复字符
			beginIdx = beginIdx + idx + 1
		}
	}

	return maxLen
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

map 方案

思路:利用 map 方案的目的是借用于 map 的 key 不能重复的特性,若出现重复的元素,删除掉该重复元素和之前的全部元素,统计 map 的长度即可。

该思路没有滑动窗口方法优秀,也在 LeetCode 上测试通过。

代码实现为:

func lengthOfLongestSubstring1(s string) int {
	// 当前最大长度
	maxLen := 0
	substr := map[byte]int{}
	beginIdx := 0
	// 遍历整个字符串
	for i, l := 0, len(s); i < l; i++ {
		if ii, exists := substr[s[i]]; exists {
			// 重复的字符
			if l := len(substr); l>maxLen {
				// 记录长度
				maxLen = l
			}
			// 确定重新统计的位置
			for di := ii; di >= beginIdx; di -- {
				delete(substr, s[di])
			}
			beginIdx = ii + 1
		}
		// 记录该字符,同时记录该字符的索引位置
		substr[s[i]] = i
	}
	if l := len(substr); l>maxLen {
		maxLen = l
	}

	return maxLen
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28