3. Longest Substring Without Repeating Characters
Hash Table, String, Sliding Window, Review ·Problem Statement
link: LeetCode.cn LeetCode
Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
Input: s = "bbbbb"
Output: 1
Input: s = "pwwkew"
Output: 3
Solution Approach
The algorithm efficiently utilizes a sliding window technique to find the longest substring without repeating characters, maintaining the window boundaries and updating the maximum length accordingly.
Algorithm
- The algorithm initializes a dictionary to store the most recent index of each character encountered.
- It defines a sliding window represented by two pointers, ‘left’ and ‘right’, to iterate over the string.
- As the window expands, it updates the maximum length of the substring without repeating characters and adjusts the ‘left’ pointer when a repeating character is encountered, ensuring no repeating characters are within the window.
Implement
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
visited = {}
left = 0
res = 0
for i, c in enumerate(s):
if c in visited and left <= visited[c]:
left = visited[c] + 1
else:
res = max(res, i - left + 1)
visited[c] = i
return res