Description#
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.
Solutions#
Solution 1: Two pointers + Hash Table#
Define a hash table to record the characters in the current window. Let $i$ and $j$ represent the start and end positions of the non-repeating substring, respectively. The length of the longest non-repeating substring is recorded by ans.
For each character $s[j]$ in the string s, we call it $c$. If $c$ exists in the window $s[i..j-1]$, we move $i$ to the right until $s[i..j-1]$ does not contain c. Then we add c to the hash table. At this time, the window $s[i..j]$ does not contain repeated elements, and we update the maximum value of ans.
Finally, return ans.
The time complexity is $O(n)$, where $n$ represents the length of the string s.
Two pointers algorithm template:
1
2
3
4
5
6
| for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(j, i)) {
++j;
}
// logic of specific problem
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ss = set()
i = ans = 0
for j, c in enumerate(s):
while c in ss:
ss.remove(s[i])
i += 1
ss.add(c)
ans = max(ans, j - i + 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) {
Set<Character> ss = new HashSet<>();
int i = 0, ans = 0;
for (int j = 0; j < s.length(); ++j) {
char c = s.charAt(j);
while (ss.contains(c)) {
ss.remove(s.charAt(i++));
}
ss.add(c);
ans = Math.max(ans, j - i + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> ss;
int i = 0, ans = 0;
for (int j = 0; j < s.size(); ++j) {
while (ss.count(s[j])) ss.erase(s[i++]);
ss.insert(s[j]);
ans = max(ans, j - i + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func lengthOfLongestSubstring(s string) int {
ss := map[byte]bool{}
i, ans := 0, 0
for j := 0; j < len(s); j++ {
for ss[s[j]] {
ss[s[i]] = false
i++
}
ss[s[j]] = true
ans = max(ans, j-i+1)
}
return ans
}
|
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
20
21
| use std::collections::HashSet;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let s = s.as_bytes();
let mut set = HashSet::new();
let mut i = 0;
s
.iter()
.map(|c| {
while set.contains(&c) {
set.remove(&s[i]);
i += 1;
}
set.insert(c);
set.len()
})
.max()
.unwrap_or(0) as i32
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
const ss = new Set();
let i = 0;
let ans = 0;
for (let j = 0; j < s.length; ++j) {
while (ss.has(s[j])) {
ss.delete(s[i++]);
}
ss.add(s[j]);
ans = Math.max(ans, j - i + 1);
}
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public int LengthOfLongestSubstring(string s) {
var ss = new HashSet<char>();
int i = 0, ans = 0;
for (int j = 0; j < s.Length; ++j)
{
while (ss.Contains(s[j]))
{
ss.Remove(s[i++]);
}
ss.Add(s[j]);
ans = Math.Max(ans, j - i + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$max = 0;
for ($i = 0; $i < strlen($s); $i++) {
$chars = [];
$sub = '';
for ($j = $i; $j < strlen($s); $j++) {
if (in_array($s[$j], $chars)) {
break;
}
$sub .= $s[$j];
$chars[] = $s[$j];
}
if (strlen($sub) > $max) {
$max = strlen($sub);
}
}
return $max;
}
}
|
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 map = [Character: Int]()
var currentStartingIndex = 0
var i = 0
var maxLength = 0
for char in s {
if map[char] != nil {
if map[char]! >= currentStartingIndex {
maxLength = max(maxLength, i - currentStartingIndex)
currentStartingIndex = map[char]! + 1
}
}
map[char] = i
i += 1
}
return max(maxLength, i - currentStartingIndex)
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| proc lengthOfLongestSubstring(s: string): int =
var
i = 0
j = 0
res = 0
literals: set[char] = {}
while i < s.len:
while s[i] in literals:
if s[j] in literals:
excl(literals, s[j])
j += 1
literals.incl(s[i]) # Uniform Function Call Syntax f(x) = x.f
res = max(res, i - j + 1)
i += 1
result = res # result has the default return value
|
Solution 2#
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;
}
|
