LeetCode Solution: 3. Longest Substring Without Repeating Characters

Cracking LeetCode 3: The Longest Substring Without Repeating Characters (A Sliding Window Adventure!)

Hey Devs! 👋 Ever stumbled upon a LeetCode problem that looks simple but hides a powerful algorithmic pattern? Today, we're diving into LeetCode problem #3, "Longest Substring Without Repeating Characters." This classic problem is a fantastic introduction to a super common and efficient technique: the Sliding Window.

Don't worry if that sounds intimidating – we'll break it down piece by piece, like LEGOs! By the end of this post, you'll not only understand the solution but also gain a valuable tool for tackling similar string and array problems. Let's get started!

The Problem: Unpacking "Longest Substring Without Repeating Characters"

Imagine you're given a string, like "abcabcbb". Your mission, should you choose to accept it, is to find the longest substring within it that doesn't have any character repeated.

Let's clarify some terms:

• Substring: A contiguous sequence of characters within a string. "abc" is a substring of "abcabcbb", but "acb" is not.
• Without Repeating Characters: Every character in our chosen substring must be unique. No 'a' appearing twice, no 'b' appearing twice, etc.

Examples to make it crystal clear:

• Input: s = "abcabcbb"

  • "abc" is a substring without repeating characters (length 3).
  • "bca" is also valid (length 3).
  • "abcab" is NOT valid because 'a' and 'b' repeat.
  • The longest one we can find is "abc" (or "bca", "cab"), with a length of 3.

• Input: s = "bbbbb"

  • The longest substring without repeating characters is just "b" (length 1).

• Input: s = "pwwkew"

  • "pwke" is NOT a substring; it's a subsequence (characters appear in order but not necessarily contiguously).
  • "wke" IS a substring without repeating characters (length 3).
  • "pww" has repeating 'w'.
  • The longest is "wke" (length 3).

The goal is to return just the length of this longest unique substring.

The Intuition: Why a "Sliding Window"?

If you're new to competitive programming, your first thought might be: "Let's check every possible substring!" And that's a valid starting point. You could have two loops, i and j, generating all substrings s[i:j+1], and for each, check if it has repeating characters. This would work, but it's pretty slow (think O(N^3) or O(N^2) depending on how you check uniqueness). Can we do better? Absolutely!

The "aha!" moment comes when you realize that if you have a substring s[left...right] that contains duplicate characters, you don't need to re-examine the entire string from scratch. You just need to adjust your current substring until it becomes valid again.

This is where the Sliding Window technique shines! Imagine a window "sliding" over the string. This window represents our current substring.

• We try to expand the window from the right.
• If we add a character that causes a duplicate, we shrink the window from the left until the duplicate is gone.
• At each valid step, we keep track of the maximum length our window has achieved.

The Approach: Two Pointers and a Set

Let's formalize our sliding window approach using two pointers, left and right, and a set to efficiently track characters within our current window.

1. Initialize:

   • max_length = 0: This will store our answer.
   • left = 0: This pointer marks the beginning of our current unique substring window.
   • char_set = set(): This set will hold all characters currently inside our s[left...right] window. Sets are perfect because they only store unique items and offer super fast add, remove, and in (contains) operations (average O(1) time complexity).

2. Iterate with the right pointer:

   • We'll use a for loop with right iterating from 0 to len(s) - 1. This pointer expands our window to the right.

3. Check for Duplicates and Shrink the Window:

   • Inside the loop, before adding s[right] to our char_set, we need to check if s[right] is already in char_set.
   • If s[right] is ALREADY in char_set: This means we have a duplicate! Our current window s[left...right-1] was unique, but s[right] broke the rule.
     • To fix this, we need to shrink the window from the left.
     • We repeatedly remove s[left] from char_set and increment left until s[right] is no longer a duplicate within our window.
     • Think of it as kicking out characters from the left until the culprit (the first instance of the duplicate) is gone.

4. Expand the Window and Update Max Length:

   • Once s[right] is guaranteed to be unique within our current (possibly shrunken) window, add s[right] to char_set.
   • Now, our current window s[left...right] is valid (all unique characters). Calculate its length: right - left + 1.
   • Update max_length = max(max_length, right - left + 1).

5. Return max_length: After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters.

Let's trace s = "abcabcbb":

right	s[right]	char_set (before s[right] check)	s[right] in char_set?	char_set (after fix)	left (after fix)	char_set (after add s[right])	Current Window (s[left...right])	Current Length	max_length
0	a	{}	False	{}	0	{a}	a	1	1
1	b	{a}	False	{a}	0	{a, b}	ab	2	2
2	c	{a, b}	False	{a, b}	0	{a, b, c}	abc	3	3
3	a	{a, b, c}	True (a repeats)	{b, c}	1	{b, c, a}	bca	3	3
4	b	{b, c, a}	True (b repeats)	{c, a}	2	{c, a, b}	cab	3	3
5	c	{c, a, b}	True (c repeats)	{a, b}	3	{a, b, c}	abc	3	3
6	b	{a, b, c}	True (b repeats)	{c}	5	{c, b}	cb	2	3
7	b	{c, b}	True (b repeats)	{}	7	{b}	b	1	3

Finally, max_length is 3! This matches the example.

The Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set() # To store characters in the current window
        left = 0         # Left pointer of the sliding window
        max_length = 0   # Stores the maximum length found so far

        for right in range(len(s)):
            # While the character at 'right' is already in our set (duplicate detected)
            while s[right] in char_set:
                # Remove the character at 'left' from the set
                char_set.remove(s[left])
                # Move the 'left' pointer to shrink the window
                left += 1

            # Add the current character at 'right' to the set
            # Now, the window s[left...right] is guaranteed to have unique characters
            char_set.add(s[right])

            # Update the maximum length found
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

This is where the sliding window truly shines!

• Time Complexity: O(N)

  • The right pointer iterates through the string s exactly once, performing N steps.
  • The left pointer also iterates through the string at most once (it only moves forward).
  • Each character is added to the char_set once and removed from the char_set at most once.
  • set operations (add, remove, check in) take average O(1) time.
  • Therefore, the total time complexity is linear, O(N), where N is the length of the string s. This is super efficient!

• Space Complexity: O(min(N, M))

  • char_set stores characters from the current window.
  • In the worst case, if all characters are unique, the set could store up to N characters (where N is len(s)).
  • However, the maximum size of the char_set is also limited by the size of the character set (e.g., 26 for lowercase English letters, 128 for ASCII, 256 for extended ASCII). Let M be the size of the alphabet.
  • So, the space complexity is O(min(N, M)). For typical interview problems dealing with ASCII characters, this is often considered O(1) constant space because M (e.g., 128 or 256) is a fixed constant regardless of the input string's length.

Key Takeaways

1. Sliding Window Power: This problem is a perfect introduction to the sliding window pattern. Remember it for problems involving finding optimal subarrays or substrings.
2. Two Pointers: The left and right pointers are crucial for defining and moving the window efficiently.
3. Hash Set (Set) for Uniqueness: A set is your best friend when you need to quickly check for the presence of an element and ensure uniqueness. Its O(1) average time complexity for lookups, insertions, and deletions is key to the overall efficiency.
4. Distinguish Substring vs. Subsequence: Always pay attention to whether the problem asks for a substring (contiguous) or a subsequence (order preserved, not necessarily contiguous).

Congratulations! You've successfully navigated one of LeetCode's most popular problems and added the powerful Sliding Window technique to your algorithmic toolkit. Keep practicing, and these patterns will become second nature!

---

Published by p1Hzd8mRM8 on 2026-05-16 23:00:35