This approach uses a two-pointer technique (often called a sliding window) to efficiently find the longest substring without repeating characters. The idea is to keep moving a start pointer to the right, while expanding the end pointer, ensuring all characters between the two pointers are unique.
Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice, once by the start pointer and once by the end pointer.
Space Complexity: O(1), since we use a fixed array of size 128 for ASCII characters.
1class Solution:
2 def lengthOfLongestSubstring(self, s: str) -> int:
3 char_index = {}
4 max_len = 0
5 start = 0
6 for end, char in enumerate(s):
7 if char in char_index:
8 start = max(start, char_index[char] + 1)
9 char_index[char] = end
10 max_len = max(max_len, end - start + 1)
11 return max_len
12
13sol = Solution()
14print(sol.lengthOfLongestSubstring("abcabcbb")) # Output: 3
15print(sol.lengthOfLongestSubstring("bbbbb")) # Output: 1
16print(sol.lengthOfLongestSubstring("pwwkew")) # Output: 3
17The Python solution uses a dictionary to map each character to its latest index. The start pointer helps maintain the substring without duplicates by skipping over repeated characters.