Hey there, fellow coders! Today, we will solve an interesting problem called "Longest Substring Without Repeating Characters". The problem requires us to find the length of the longest substring without repeating characters in a given string.
Problem Description
Given a string s, find the length of the longest substring without repeating characters.
Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Solution
We will solve this problem using the sliding window technique. We will maintain two pointers, left and right, which will define the current window. We will also maintain a set to keep track of the unique characters in the current window.
Initialize left and right pointers to 0, and an empty set.
Loop through the string s, until the right pointer reaches the end of the string.
Check if the character at the right pointer is already present in the set.
If yes, remove the character at the left pointer from the set and increment the left pointer by 1.
If no, add the character at the right pointer to the set and increment the right pointer by 1.
At each iteration, update the length of the longest substring without repeating characters.
Here's the Python code for the same:
def lengthOfLongestSubstring(s: str) -> int:
left, right = 0, 0
unique_chars = set()
max_len = 0
while right < len(s):
if s[right] not in unique_chars:
unique_chars.add(s[right])
right += 1
max_len = max(max_len, len(unique_chars))
else:
unique_chars.remove(s[left])
left += 1
return max_len
Complexity Analysis
Time Complexity: O(n), where n is the length of the input string. We traverse the string once, and each character is visited at most twice.
Space Complexity: O(min(m, n)), where m is the size of the character set. In the worst-case scenario, all characters are unique, and the space required is O(n).
Conclusion
We have successfully solved the Longest Substring Without Repeating Characters problem from LeetCode using the sliding window technique. Hope you found the solution intuitive and easy to understand. Keep coding! 😎