[算法训练]LeetCode 3: 无重复字符的最长子串

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

无重复字符的最长子串

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

示例 1:

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

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

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

Related Topics: 字符串 滑动窗口

思路

惯例,首先思考一下暴力方法,是会超时还是爆内存,再考虑优化的方法。

暴力方法

遍历每一个字符ai,再往后遍历aj ( j > i ),如果存在aj = ak ( i ≤ k < j ),则比较之前长度的最大值并保存,maxLength = max(maxLength, j - i)

最坏的情况下,时间复杂度为O(n3)

优化

很显然,暴力算法做了很多重复工作,比如

abcabcbb

当找到第二个a的时候,我们已经知道这两个a之间的字符b c是没有重复的,所以不用再反复比较了。

自然而然会想到用滑动窗口的方式来优化。

1
2
3
abcabcbb → abcabcbb → abcabcbb → abcabcbb
↑↑ → ↑ ↑ → ↑ ↑ → ↑ ↑
ij → i j → i j → i j

用两个指针i和j,让j开始向后滑动,当出现j指向的内容与前面重复(即aj = ak ( i ≤ k < j ) ),则将i往后移动一位,在移动过程中j-i的最大值就是答案。

但是关键是怎么快速判断是否重复,重新审题,字符都是ASCII码,所以可以构造一个长度为256的布尔数组(甚至128就够了),该字符的ASCII码数值则为索引,值用来标记是否已经访问过。

在j往后移动的过程中,将arr[a[j]]设置为true;

在i往后移动的过程中,将前一位arr[a[i-1]]设置为false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def lengthOfLongestSubstring(self, s):
a = [False] * 256
length = len(s)
i, j = 0, 0
res = 0
while j < length:
if i < j and a[ord(s[j])]:
a[ord(s[i])] = False
i += 1
else:
a[ord(s[j])] = True
j += 1
res = max(res, j - i)
return res

如果大家有更好的解法,恳请不吝赐教,谢谢!

0%