Longest Substring Without Repeat
Given a string s, write a function longestSubstringWithoutRepeat that returns the length of the longest substring without repeating characters. You may assume that the input string contains only ASCII characters. If the string is empty, return 0. The substring must consist of contiguous characters, and it cannot include any duplicate characters.
Examples
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Input: s = "" Output: 0 Explanation: The string is empty, so the answer is 0.
Can you come up with a solution with a O(n) time complexity?
Our solution processes the input string by iterating through it while maintaining a set of characters (char_set) that tracks the unique characters in the current window (substring without repeating characters). We use two pointers (left and right) to define the boundaries of this sliding window.
- For each character
s[right]in the string, we check whether it is already present inchar_set. - If the character is already present, we remove characters from the left side of the window (i.e., we increment the
leftpointer) until the repeating character is removed fromchar_set. - After ensuring there are no repeating characters in the current window, we add
s[right]tochar_set. - We then update the maximum length of the substring found so far by comparing the current window size (
right - left + 1) with the previous maximum length.
By maintaining a sliding window that expands and contracts dynamically as we move through the string, we can efficiently determine the length of the longest substring without repeating characters.
def longest_substring_without_repeat(s: str) -> int:
char_set = set() # To keep track of unique characters in the current window
left = 0 # Left pointer for the sliding window
max_length = 0 # To track the maximum length of substring found
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_lengthTime Complexity:
The time complexity of this solution is O(n), where n is the length of the string. Each character in the string is added to and removed from the char_set at most once, resulting in a linear pass through the string.
Space Complexity:
The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set (i.e., 128 for ASCII or 256 for extended ASCII). This is because, in the worst case, we may need to store up to m unique characters in the set.
Check out our lesson on the sliding window approach to learn more about what it is and how to use it!
we can use two pointer + set like maintain i,j and also insert jth character to set like while set size is equal to our window j-i+1 then maximize our answer and increase jth pointer till last index