Longest Substring Without Repeating Charactersbb
|Last edited: 2024-4-26
ID
3
Data Type
Two Pointer
Difficulty
Medium
Tags
Hash Table
Sliding Window
URL
Completed Date
Feb 22, 2024
Preference
💕 Like
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Example 2:
Example 3:
Constraints:
  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.
 
This Go code solves the problem of finding the length of the longest substring without repeating characters using a technique called the sliding window algorithm. Here's a detailed explanation of the code:
  1. res, left, right, strLen := 0, 0, -1, len(s): This line initializes four variables. res is used to store the length of the longest substring without repeating characters found so far. left and right are the indices that define the boundaries of the current window (substring). strLen is the length of the input string s.
  1. if strLen == 0 { return 0 }: If the length of the input string is 0, the function returns 0 because there's no substring in an empty string.
  1. var freq [127]int: This line declares a frequency array freq of size 127 (enough to cover all ASCII characters). This array is used to keep track of the frequency of each character in the current window.
  1. The for loop continues as long as left is less than strLen, which means there are still characters to consider in the string.
  1. Inside the for loop, the code checks if right+1 is less than strLen and the character at s[right+1] hasn't appeared in the current window (i.e., freq[s[right+1]] == 0). If both conditions are true, it increments the frequency of the character at s[right+1], and moves right one step to the right. If either condition is not true, it decrements the frequency of the character at s[left], and moves left one step to the right, effectively shrinking the window from the left.
  1. res = max(res, right-left+1): After each operation, it updates res with the maximum value between the current res and the length of the current window (right-left+1).
  1. Finally, it returns res, which is the length of the longest substring without repeating characters.
This code effectively checks each substring of the input string by moving the window from left to right, and keeps track of the longest substring without repeating characters. By using a frequency array to keep track of the characters in the current window, it ensures that the window always represents a substring without repeating characters.
 
 
 
 

Validation function

 
 

abcabcbb

left
right
freq
s[left:right+1]
select range
len
res
max
0
0
a:1, b:0, c:0
a
<a>bcabcbb
1
0
1
0
1
a:1, b:1, c:0
ab
<ab>cabcbb
2
1
2
0
2
a:1, b:1, c:1
abc
<abc>abcbb
3
2
3
1
2
a:0, b:1, c:1
bc
a<bc>abcbb
2
3
3
1
3
a:1, b:1, c:1
bca
a<bca>bcbb
3
3
3
2
3
a:1, b:0, c:1
ca
ab<ca>bcbb
2
3
3
2
4
a:1, b:1, c:1
cab
ab<cab>cbb
3
3
3
3
4
a:1, b:1, c:0
ab
abc<ab>cbb
2
3
3
3
5
a:1, b:1, c:1
abc
abc<abc>bb
3
3
3
4
5
a:0, b:1, c:1
bc
abca<bc>bb
2
3
3
5
5
a:0, b:0, c:1
c
abcab<c>bb
1
3
3
5
6
a:0, b:1, c:1
cb
abcab<cb>b
2
3
3
6
6
a:0, b:1, c:0
b
abcabc<b>b
1
3
3
7
6
a:0, b:0, c:0
ㅤ
abcabcb<>b
0
3
3
7
7
a:0, b:1, c:0
b
abcabcb<b>
1
3
3
8
7
a:0, b:0, c:0
ㅤ
abcabcbb<>
0
3
3

abcbbcc

left
right
freq
s[left:right+1]
select range
len
res
max
0
0
a:1, b:0, c:0
a
<a>bcbbcc
1
0
1
0
1
a:1, b:1, c:0
ab
<ab>cbbcc
2
1
2
0
2
a:1, b:1, c:1
abc
<abc>bbcc
3
2
3
1
2
a:0, b:1, c:1
bc
a<bc>bbcc
2
3
3
2
2
a:0, b:0, c:1
c
ab<c>bbcc
1
3
3
2
3
a:0, b:1, c:1
cb
ab<cb>bcc
2
3
3
3
3
a:0, b:1, c:0
b
abc<b>bcc
1
3
3
4
3
a:0, b:0, c:0
ㅤ
abcb<>bcc
0
3
3
4
4
a:0, b:1, c:0
b
abcb<b>cc
1
3
3
4
5
a:0, b:1, c:1
bc
abcb<bc>c
2
3
3
5
5
a:0, b:0, c:1
c
abcbb<c>c
1
3
3
6
5
a:0, b:0, c:0
ㅤ
abcbbc<>c
0
3
3
6
6
a:0, b:0, c:1
c
abcbbc<c>
1
3
3
7
6
a:0, b:0, c:0
ㅤ
abcbbcc<>
0
3
3
 
策略是“吐了再吞”，如果发现前面的字符在字符组里，因为要求连续，所以就必须先把吞进去的吐干净，不吐干净就没法吞新的