Longest Substring Without Repeating Characters - Leetcode Solution

Problem statement:

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.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution:

To find the longest substring without repeating characters, we can use the sliding window approach. In this approach, we maintain a sliding window of characters in the string, and keep track of the characters we have already seen in a set.

We start with an empty set, an empty substring, and the start of the window at the beginning of the string. We then move the end of the window forward until we find a repeating character. When we encounter a repeating character, we remove the first character of the substring from the set and move the start of the window forward. We keep track of the length of the longest substring we have seen so far.

Here is the Python code for the solution:

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: seen = set() start = 0 max_len = 0

    for end in range(len(s)):
        while s[end] in seen:
            seen.remove(s[start])
            start += 1
            
        seen.add(s[end])
        max_len = max(max_len, end-start+1)
    
    return max_len

We initialize an empty set seen to keep track of the characters we have already seen, and start at the beginning of the string with the start of the window set to 0. We also initialize the maximum length of the substring seen so far to 0.

We then loop through the string, with end as the index of the end of the window. We add the character at the end of the window to the set seen, and update the maximum length of the substring seen so far if necessary.

If the character at the end of the window is already in seen, we remove the first character of the substring (at the start of the window) from seen and move the start of the window forward. We repeat this until the character at the end of the window is not in seen anymore.

Finally, we return the maximum length of the substring seen so far.

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string s. We process each character in the string once, and the set operations take constant time on average.

Space Complexity:

The space complexity of this solution is O(min(n, m)), where n is the length of the input string s and m is the size of the character set (26 for English alphabet). In the worst case, the input string contains all unique characters, so the space complexity is O(n). In the best case, the input string contains only one character, so the space complexity is O(1).

1