LeetCode3——无重复字符的最长子串

问题描述

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

示例

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

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

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

解题思路:

1.暴力法

暴力法就是取出所有的子串,判断其是否无重复字符,然后记录无重复字符的子串的最大长度。遍历所有的子串,可以枚举他们的开始索引i和结束索引j,0 <= i < j <= n,用两层嵌套循环,依次取出子串,判断其是否无重复字符,同时记录和更新无重复子串的长度最大值。

2.滑动窗口HashSet

在暴力法中,我们会反复检查子串是否无重复字符,但其实再i到j-1的子串已经是无重复字符的情况下,我们只需要检查S[ j ]是否已经存在于S[i, j-1]的子串中,这里可以利用HashSet,在O(1)的时间复杂度下检查。将HashSet作为滑动窗口,如果s[ j ]不在子串中,则将j向后移动一位,i不变,若在子串中,则依次从HashSet中去除S[ i ],并将i后移,直到从HashSet中去除了重复的那个字符。HashSet这个滑动窗口的长度最大值,即为最长无重复字符子串的长度。

3.滑动窗口HashMap

在第二种解法中,我们需要一步一步找到重复的那个字符,其实我们可以利用HashMap直接定位到重复字符的位置。将HashMap的key记录为字符串的字符,value记录为字符的下一个位置,如果在s[i, j)范围内有重复字符a,我们找到a字符在HashMap里的值p,直接跳过[i, p-1],将滑动窗口变为[p, j]。

代码展示

java版:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

class Solution {

//暴力法
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + i; j <= n; j++){
if(allUnique(s, i, j)){
ans = Math.max(ans, j - i);
}
}
}
return ans;
}
boolean allUnique(String s, int start, int end){
Set<Character> set = new HashSet<>();
for(int i = start; i < end; i++){
if(set.contains(s.charAt(i))){
return false;
}
set.add(s.charAt(i));
}
return true;
}

//滑动窗口hashset
public int lengthOfLongestSubstring2(String s) {
int n = s.length();
int ans = 0;
int i = 0, j = 0;
Set<Character> set = new HashSet<>();

while(i < n && j < n){
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j-i);
}
else{
set.remove(s.charAt(i++));
}
}
return ans;
}

//滑动窗口hashmap
public int lengthOfLongestSubstring3(String s) {
int n = s.length();
int ans = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0, j = 0; j < n; j++){
if(map.containsKey(s.charAt(j))){
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j-i+1);
map.put(s.charAt(j), j+1);
}
return ans;
}
}

Go版:

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

func lengthOfLongestSubstring(s string) int {
n := len(s)
var ans int
m := make(map[byte]int)
for i, j := 0, 0; j < n; j++ {
k := s[j]
if v, ok := m[k]; ok {
if v > i {
i = v
}
}
if ans < j-i+1 {
ans = j - i + 1
}
m[k] = j + 1
}
return ans
}