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

示例 1:

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

示例 2:

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

示例 3:

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

请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解法一:暴力求解

找出所有的子串,然后一个一个地去判断每个子串里是否包含有重复的字符。假设字符串的长度为 n,那么有 n×(n + 1) / 2 个非空子串。计算过程如下。

长度为 1 的子串,有 n 个

长度为 2 的子串,每两个每两个相邻地取,一共有 n - 1 个

长度为 3 的子串,每三个每三个相邻地取,一共有 n - 2 个

……

以此类推,长度为 k 的子串,有 n - k + 1 个。

当 k 等于 n 的时候,n - k + 1=1,即长度为 n 的子串有 1 个。

所有情况相加,得到所有子串的长度为:

n + (n - 1) + (n - 2) + (n - 3) + … + 2 + 1 = n×(n + 1) / 2

算上空字符串,那么就一共有 n×(n + 1) / 2 + 1 个。

拓展一下,对于一个长度为 n 的字符串,一共有多少个子序列呢?和子串不一样,子序列里的元素不需要相互挨着。

同理分析,长度为 1 的子序列有 n 个,即 Cn1,长度为 2 的子序列个数为 Cn2,以此类推,长度为 k 的子序列有 Cnk,那么所有子序列的个数(包括空序列)是 Cn0 + Cn1 + Cn2 + … Cnn = 2n

注意:对于统计子串和子序列个数的方法和结果,大家务必记下来,对于在分析各种问题时会有很大帮助。

回到本来问题,如果对所有的子串进行判断,从每个子串里寻找出最长的那个并且没有重复字符的,那么复杂度就是:O(n×(n + 1)/2×n) = O(n3)。

解法二:线性法

例题 1:给定的字符串里有一段是没有重复字符的,如下,能不能把下一个字符 a 加进来?

要看当前的子串”abc”是否已经包含了字符 a。

  1. 扫描一遍“abc”,当发现某个字符与 a 相同,可以得出结论。

  2. 把“abc“三个字符放入到一个哈希集合里,那么就能在 O(1) 的时间里作出判断,提高速度。

使用定义一个哈希集合 set 的方法,从给定字符串的头开始,每次检查一下当前字符是不是在集合里边,如果不在,说明这个字符不会造成重复和冲突,把它加入到集合里,并统计一下当前集合的长度,可能它就是最长的那个子串。

例题 2:如果发现新的字符已经在集合里已经出现了,怎么办?

deabc 是目前为止没有重复字符的最长子串,当我们遇到下一个字符a的时候,以这个字符结尾的没有重复的子串是“bca”,而此时集合里的字符有:d,e,a,b,c。首先,必须把 a 删除,因为这样才能把新的 a 加入到集合里,那么如何判断要把 d 和 e 也都删除呢?

可以定义两个指针 i 和 j。

i 是慢指针,j 是快指针,当 j 遇到了一个重复出现的字符时,从慢指针开始一个一个地将 i 指针指向的字符从集合里删除,然后判断一下是否可以把新字符加入到集合里而不会产生重复。

把字符 d 删除后,i 指针向前移动一步,此时集合里还剩下:e, a, b, c,很明显,字符 a 还在集合里,仍然要继续删除。

把字符 e 删除后,集合里还剩 a,b,c,字符 a 还在集合里,继续删除慢指针 i 指向的字符 a。

集合里剩 b,c,可以放心地把新的字符 a 放入到集合里,然后快指针 j 往前移动一步。

通过这样不断尝试,每当新的字符加入到集合里的时候,统计一下当前集合里的元素个数,最后记录下最长的那个。

时间复杂度

由于采用的是快慢指针的策略,字符串最多被遍历两次,快指针遇到的字符会被添加到哈希集合,而慢指针遇到的字符会从哈希集合里删除,对哈希集合的操作都是 O(1) 的时间复杂度,因此,整个算法的时间复杂度就是 n×O(1) + n×O(1) = O(n)。

空间复杂度

由于用到了一个哈希集合,在最坏的情况下,给定的字符串没有任何重复的字符,需要把每个字符都加入到哈希集合里,因此空间复杂度是 O(n)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 定义一个哈希集合 set,初始化结果 max 为 0
int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int max = 0;
// 用快慢指针 i 和 j 扫描一遍字符串,如果快指针所指向的字符已经出现在哈希集合里,不断地尝试将慢指针所指向的字符从哈希集合里删除
for (int i = 0, j = 0; j < s.length(); j++) {
while (set.contains(s.charAt(j))) {
set.remove(s.charAt(i));
i++;
}
// 当快指针的字符加入到哈希集合后,更新一下结果 max
set.add(s.charAt(j));
max = Math.max(max, set.size());
}
return max;
}

解法三:优化的线性法

在上述例题中,能否让慢指针不再一步一步地挪动,而是迅速地跳到字符 b 的位置?

可以用哈希表来记录每个字符以及它出现的位置,当遇到了字符 a 的时候,就知道跟它重复的前一个字符出现的位置,只需要让慢指针指向那个位置的下一个即可。(如果题目说所有字符都是字母的话,也可以用一个数组去记录。)

遇到字符 a,此时哈希表的记录 {d: 0, e: 1, a: 2, b: 3: c: 4},a 的位置是 2,把 2 加上 1 等于 3,就能让慢指针 i 指向下标为 3 的位置,即 b 字符的地方。

注意:在运用这个算法的时候,不能去数哈希集合的元素个数来作为子串的长度,所以得额外维护一个变量来保存最后的结果。

但是在一些情况下,我们不能简单地将取出来的重复位置加 1,如下:快指针 j 指向的字符是 e,而 e 在哈希表里记录的位置是 1。

在这种情况下,没有必要让 i 重新指向 e 后面的 a。此时,i 应该保留在原地不动。因此,i 被移动到的新位置应该等于 max(i,重复字符出现位置 + 1)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 定义一个哈希表用来记录上一次某个字符出现的位置,并初始化结果 max 为 0 
int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int max = 0;
// 用快慢指针 i 和 j 扫描一遍字符串,若快指针所对应的字符已经出现过,则慢指针跳跃
for (int i = 0, j = 0; j < s.length(); j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(i, map.get(s.charAt(j)) + 1);
}
map.put(s.charAt(j), j);
max = Math.max(max, j - i + 1);
}
return max;
}

立即AC

评论