Given a string s, find the length of the longest substring without repeating characters.
时间: 2024-03-03 17:47:07 浏览: 99
数据结构:第5章数组和广义表A.ppt
To find the length of the longest substring without repeating characters, we can use the sliding window approach. Here's the algorithm:
1. Initialize a set to store the unique characters in the current window, and two pointers left and right to mark the current window.
2. Initialize a variable max_len to 0 to store the length of the longest substring without repeating characters.
3. While the right pointer is less than the length of the string s:
- If the character at s[right] is not in the set, add it to the set and move the right pointer to the right.
- Else, remove the character at s[left] from the set and move the left pointer to the right.
4. Update the value of max_len with the maximum of its current value and the size of the set.
5. Return max_len.
Here's the Python code for the algorithm:
```
def longest_substring(s):
unique_chars = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in unique_chars:
unique_chars.remove(s[left])
left += 1
unique_chars.add(s[right])
max_len = max(max_len, len(unique_chars))
return max_len
```
Example usage:
```
s = "abcabcbb"
print(longest_substring(s)) # Output: 3 (for "abc")
```
阅读全文