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

题目

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

示例1:

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

示例 2:

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

示例 3:

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

示例 4:

1
2
输入: s = ""
输出: 0

提示:

  • 0 <= s.length <= 5 * 104
  • s由英文字母、数字、符号和空格组成

解题

方法

滑动窗口 + 位图

这里有两个关键点:

  • 我们设定左右两个下标 x 和 y,如果当前 x - y 的之间不包含重复字符,那么 x++ 在 x = y 之前的所有位置,左右两侧之间都不会包含重复字符

  • 判断每个位置的字符是否重复可以用位图 bitset,题目设定字符只能由英文字母、数字、符号和空格组成,256 长度的 bitset 已足够

  • 因此我们只需要遍历字符,通过判断右侧的新字符是否存在来调整左右两侧的坐标,直到已找到最大长度或者右侧字符到字符串的尾端

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
29
30
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
// 位图,默认所有位置都为false,256个已足够包含题目中的字符
bitSet := [256]bool{}
left, right, res := 0, 0, 0
for left < len(s) {
// 判断右侧位置字符对应的值是否为true
if bitSet[s[right]] {
// 如果值为true,证明这个字符已经存在,则需要左侧位进1
bitSet[s[left]] = false
left++
} else {
// 如果值为false,说明这个字符当前尚不存在,需要设置为true,并将右侧位进1
bitSet[s[right]] = true
right++
}
// 判断完后需要计算长度
if res < right-left {
res = right - left
}
// 如果左侧位置加最新的最大长度大于等于字符总长度,说明后续不可能再有比这个长度更大的连续无重复子串了
// 如果右侧位置已经到头则需要停止循环
if left+res >= len(s) || right >= len(s) {
break
}
}
return res
}

单元测试

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 测试无重复字符的最长子串
func TestLengthOfLongestSubstring(t *testing.T) {
type args struct {
s string
}
tests := []struct {
name string
args args
want int
}{
{
name: "01",
args: args{
s: "abcabcbb",
},
want: 3,
},
{
name: "02",
args: args{
s: "bbbbb",
},
want: 1,
},
{
name: "03",
args: args{
s: "pwwkew",
},
want: 3,
},
{
name: "04",
args: args{
s: "",
},
want: 0,
},
}
for _, tt := range tests {
t.Run(
tt.name, func(t *testing.T) {
if got := lengthOfLongestSubstring(tt.args.s); got != tt.want {
t.Errorf("lengthOfLongestSubstring() = %v, want %v", got, tt.want)
}
},
)
}
}

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
=== RUN   TestLengthOfLongestSubstring
--- PASS: TestLengthOfLongestSubstring (0.00s)
=== RUN TestLengthOfLongestSubstring/01
--- PASS: TestLengthOfLongestSubstring/01 (0.00s)
=== RUN TestLengthOfLongestSubstring/02
--- PASS: TestLengthOfLongestSubstring/02 (0.00s)
=== RUN TestLengthOfLongestSubstring/03
--- PASS: TestLengthOfLongestSubstring/03 (0.00s)
=== RUN TestLengthOfLongestSubstring/04
--- PASS: TestLengthOfLongestSubstring/04 (0.00s)
PASS

Process finished with exit code 0

总结

这个题目用到了 滑动窗口位图bitset 来处理

时间复杂度:O(N),其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度:O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。本题解法中包含了所有 ASCII 码在 [0, 256) 内的字符,即 ∣Σ∣=256。

本文作者:Jormin
本文地址https://blog.lerzen.com/leetcode-无重复字符的最长子串/
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!

----- 到这结束咯 感谢您的阅读 -----