LeetCode #3: Longest Substring Without Repeating Characters

LeetCode Solutions

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

To solve this problem in Python 3, we can use a sliding window approach that involves maintaining a set of unique characters and expanding the window until we encounter a repeating character.

Here are the steps to follow:

  1. Initialize two pointers, left and right, to the start of the string.
  2. Initialize an empty set, chars, to store the unique characters in the current substring.
  3. Initialize the max_len variable to 0.
  4. Iterate through the string using the right pointer and add each character to the chars set. If a repeating character is encountered, remove the leftmost character from the chars set and increment the left pointer until the repeating character is no longer in the chars set.
  5. Update the max_len variable with the length of the current substring.
  6. Return the max_len.

Here’s the Python 3 code that implements this approach:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = right = 0
        chars = set()
        max_len = 0
        while right < len(s):
            if s[right] not in chars:
                chars.add(s[right])
                right += 1
                max_len = max(max_len, len(chars))
            else:
                chars.remove(s[left])
                left += 1
        return max_len

In this code, we initialize the left and right pointers to the start of the string, the chars set to an empty set, and the max_len variable to 0. We then iterate through the string using the right pointer and add each character to the chars set. If a repeating character is encountered, we remove the leftmost character from the chars set and increment the left pointer until the repeating character is no longer in the chars set. We then update the max_len variable with the length of the current substring and return it.

Time and Space Complexity:

The time complexity of this solution is O(n), where n is the length of the string s. This is because we only iterate through the string once.

The space complexity of this solution is O(k), where k is the size of the character set. In the worst case, where all characters are unique, the space complexity is O(n), where n is the length of the string s.