Longest Substring Without Repeating Charactersbb
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 longestsubstring
without repeating characters.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= s.length <= 5 * 10
4
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:
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
andright
are the indices that define the boundaries of the current window (substring).strLen
is the length of the input strings
.
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.
var freq [127]int
: This line declares a frequency arrayfreq
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.
- The
for
loop continues as long asleft
is less thanstrLen
, which means there are still characters to consider in the string.
- Inside the
for
loop, the code checks ifright+1
is less thanstrLen
and the character ats[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 ats[right+1]
, and movesright
one step to the right. If either condition is not true, it decrements the frequency of the character ats[left]
, and movesleft
one step to the right, effectively shrinking the window from the left.
res = max(res, right-left+1)
: After each operation, it updatesres
with the maximum value between the currentres
and the length of the current window (right-left+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 |
策略是“吐了再吞”,如果发现前面的字符在字符组里,因为要求连续,所以就必须先把吞进去的吐干净,不吐干净就没法吞新的