题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
注意：本题与主站 3 题相同：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
解法
方法一：双指针 + 哈希表
我们用双指针 $j$ 和 $i$ 分别表示子串的左右边界，其中 $j$ 是滑动窗口的左边界，$i$ 是滑动窗口的右边界，用哈希表 $vis$ 记录每个字符是否出现过。
遍历字符串 $s$，如果此时 $s[i]$ 在哈希表 $vis$ 中存在，说明 $s[i]$ 重复了，我们需要将左边界 $j$ 右移，直到 $s[i]$ 不在哈希表 $vis$ 中为止，然后将 $s[i]$ 加入哈希表 $vis$ 中。此时，我们更新无重复字符子串的最大长度，即 $ans = \max(ans, i - j + 1)$。
遍历结束后，我们返回 $ans$ 即可。
时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 是字符串 $s$ 的长度；而 $C$ 是字符集的大小。
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
cnt = Counter()
ans = j = 0
for i, c in enumerate(s):
cnt[c] += 1
while cnt[c] > 1:
cnt[s[j]] -= 1
j += 1
ans = max(ans, i - j + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0, j = 0;
Set<Character> vis = new HashSet<>();
for (int i = 0; i < s.length(); ++i) {
while (vis.contains(s.charAt(i))) {
vis.remove(s.charAt(j++));
}
vis.add(s.charAt(i));
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
unordered_set<char> vis;
for (int i = 0, j = 0; i < s.size(); ++i) {
while (vis.count(s[i])) {
vis.erase(s[j++]);
}
vis.insert(s[i]);
ans = max(ans, i - j + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func lengthOfLongestSubstring(s string) (ans int) {
vis := map[byte]bool{}
j := 0
for i := range s {
for vis[s[i]] {
vis[s[j]] = false
j++
}
vis[s[i]] = true
ans = max(ans, i-j+1)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | function lengthOfLongestSubstring(s: string): number {
let ans = 0;
const vis = new Set<string>();
for (let i = 0, j = 0; i < s.length; ++i) {
while (vis.has(s[i])) {
vis.delete(s[j++]);
}
vis.add(s[i]);
ans = Math.max(ans, i - j + 1);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | use std::collections::HashSet;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut set = HashSet::new();
let mut res = 0;
let mut i = 0;
for j in 0..n {
while set.contains(&s[j]) {
set.remove(&s[i]);
i += 1;
}
set.insert(s[j]);
res = res.max(set.len());
}
res as i32
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | /**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let ans = 0;
const vis = new Set();
for (let i = 0, j = 0; i < s.length; ++i) {
while (vis.has(s[i])) {
vis.delete(s[j++]);
}
vis.add(s[i]);
ans = Math.max(ans, i - j + 1);
}
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | public class Solution {
public int LengthOfLongestSubstring(string s) {
var vis = new HashSet<char>();
int ans = 0;
for (int i = 0, j = 0; i < s.Length; ++i) {
while (vis.Contains(s[i])) {
vis.Remove(s[j++]);
}
vis.Add(s[i]);
ans = Math.Max(ans, i - j + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
var ans = 0
var j = 0
var vis = Set<Character>()
let sArray = Array(s)
for i in 0..<sArray.count {
while vis.contains(sArray[i]) {
vis.remove(sArray[j])
j += 1
}
vis.insert(sArray[i])
ans = max(ans, i - j + 1)
}
return ans
}
}
|
方法二
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
vis = set()
ans = j = 0
for i, c in enumerate(s):
while c in vis:
vis.remove(s[j])
j += 1
vis.add(c)
ans = max(ans, i - j + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int lengthOfLongestSubstring(String s) {
boolean[] ss = new boolean[128];
int ans = 0, j = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
while (ss[c]) {
ss[s.charAt(j++)] = false;
}
ans = Math.max(ans, i - j + 1);
ss[c] = true;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
int lengthOfLongestSubstring(string s) {
bool ss[128] = {false};
int n = s.size();
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (ss[s[i]]) {
ss[s[j++]] = false;
}
ss[s[i]] = true;
ans = max(ans, i - j + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func lengthOfLongestSubstring(s string) (ans int) {
ss := make([]bool, 128)
j := 0
for i, c := range s {
for ss[c] {
ss[s[j]] = false
j++
}
ss[c] = true
ans = max(ans, i-j+1)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function lengthOfLongestSubstring(s: string): number {
let ans = 0;
const n = s.length;
const ss: boolean[] = new Array(128).fill(false);
for (let i = 0, j = 0; i < n; ++i) {
while (ss[s[i]]) {
ss[s[j++]] = false;
}
ss[s[i]] = true;
ans = Math.max(ans, i - j + 1);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | use std::collections::HashMap;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut map = HashMap::new();
let mut res = 0;
let mut i = -1;
for j in 0..n {
let c = s[j];
let j = j as i32;
if map.contains_key(&c) {
i = i.max(*map.get(&c).unwrap());
}
map.insert(c, j);
res = res.max(j - i);
}
res
}
}
|