3. Longest Substring Without Repeating Characters (Medium)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0

        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_length

# Example Usage:
sol = Solution()
print(sol.lengthOfLongestSubstring("abcabcbb")) # Output: 3 ("abc")
print(sol.lengthOfLongestSubstring("bbbbb"))    # Output: 1 ("b")
print(sol.lengthOfLongestSubstring("pwwkew"))   # Output: 3 ("wke")

Output Clear

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0

        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_length

Function Description

Source code in python/_3.py

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0

        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_length

lengthOfLongestSubstring(s)

Source code in python/_3.py

def lengthOfLongestSubstring(self, s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    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_length

Explanation

The "Longest Substring Without Repeating Characters" problem is a foundational algorithmic challenge that requires finding the maximum length of a substring within a given input string \(s\) that contains no repeated characters. This problem is an excellent measure of a developer's ability to identify and implement time-efficient solutions. While a simple brute-force check of all possible substrings yields a highly inefficient time complexity of \(O(n^3)\) or a slightly better \(O(n^2)\), professional standards demand an optimized solution that can handle large inputs, specifically one that operates in linear time, \(O(n)\).

The standard, most robust approach for solving this problem involves the Sliding Window technique. This method utilizes two pointers, left and right, to dynamically define the current substring window. To ensure rapid checks for character uniqueness, a hash set (or a map) is used to track the characters currently residing within the window, leveraging its \(O(1)\) average-time lookup capability. The right pointer iterates through the string, expanding the window one character at a time. As the window expands, the current length is continuously compared against and updates the global maximum length found so far.

The key to the \(O(n)\) efficiency lies in how the algorithm handles duplicates. If the character at \(s[right]\) is already present in the hash set, the uniqueness constraint is violated. Instead of discarding all previous work, the left pointer advances, removing characters from the left side of the window (and the hash set) until the duplicate character that caused the collision is finally removed. Once the window is again valid, the right pointer continues its forward movement. Because each character is visited by both the left and right pointers at most once, this single-pass, two-pointer strategy guarantees the sought-after \(O(n)\) time complexity, making it the industry-standard solution.