Hommies

Posted on May 16

LeetCode Solution: 3. Longest Substring Without Repeating Characters

#leetcode #dsa #programming #tutorial

Sliding into Success: Solving LeetCode 3 - Longest Substring Without Repeating Characters

Hey there, aspiring competitive programmers and curious coders!

Today, we're diving into a classic LeetCode problem that's a fantastic introduction to a super useful technique: the Sliding Window. It's problem #3, "Longest Substring Without Repeating Characters," and it's a rite of passage for many!

Don't let the name intimidate you. By the end of this post, you'll not only understand it but also appreciate the elegance of its solution.

Problem Explanation: What are we actually trying to find?

The problem asks us to find the length of the longest substring within a given string s that doesn't have any repeating characters.

Let's break down some keywords:

String s: This is our input, like "abcabcbb" or "pwwkew".
Substring: This is a contiguous sequence of characters within a string. For example, in "abc", "a", "ab", "bc", "abc" are substrings. "ac" is not a substring because the characters aren't consecutive.
Without repeating characters: Every character in our substring must be unique. If we see 'a', we can't have another 'a' in the same substring.

Let's look at the examples:

s = "abcabcbb"
- "abc" is a substring without repeating characters (length 3).
- "bca" is also a substring without repeating characters (length 3).
- The longest such substring has a length of 3.
s = "bbbbb"
- "b" is the longest substring without repeating characters (length 1).
s = "pwwkew"
- "pw" (length 2)
- "wke" (length 3) - This is our winner!
- "kew" (length 3) - Another winner!
- IMPORTANT: "pwke" is not a substring, it's a subsequence. Remember, substrings must be contiguous. "wke" is valid because 'w', 'k', 'e' are consecutive.

Our goal is to return just the length of this longest unique-character substring.

Intuition: The "Aha!" Moment

Imagine you're looking at a street. You want to find the longest stretch of unique houses (characters). You start walking, adding each new house you see to your mental list.

If you see a house you've already listed, you know your current unique stretch has ended at or before this duplicate.
To continue, you can't just skip the duplicate. You need to "forget" houses from the beginning of your current stretch until the duplicate is no longer in your list. Then, you can add the current house and keep walking.

This "walking" and "forgetting" sounds like a Sliding Window! We'll have two pointers: left and right.

right expands our window, bringing new characters in.
left shrinks our window when we encounter a duplicate, removing characters from the start until the duplicate is gone.

At each step, we'll keep track of the maximum length our window has ever achieved.

Approach: Building Our Sliding Window

We'll use two pointers, left and right, to define our current "window" (substring). We also need a way to quickly check if a character is already in our current window. A Set (or HashSet in some languages) is perfect for this, as it allows for O(1) average time complexity for add, remove, and check operations.

Here's the step-by-step logic:

Initialize:
- left = 0: This pointer marks the beginning of our current unique substring.
- max_length = 0: This will store the maximum length we've found so far.
- char_set = set(): An empty set to store characters currently within our window [left, right].
Iterate with right pointer:
- We'll use a for loop, letting right traverse the input string s from 0 to len(s) - 1. This pointer expands our window to the right.
Check for Duplicates:
- Inside the loop, before adding s[right] to our char_set, we check if s[right] is already in char_set.
- If s[right] IS in char_set (duplicate found):
  - This means our current window s[left...right-1] has a duplicate if s[right] is added.
  - To resolve this, we need to shrink our window from the left side.
  - We enter a while loop:
    - Remove s[left] from char_set.
    - Increment left by 1.
    - Repeat this until s[right] is no longer in char_set. This ensures our window s[left...right-1] is unique before we add s[right].
- If s[right] IS NOT in char_set (unique character):
  - Great! We can safely add s[right] to char_set.
Update max_length:
- After s[right] has been added (and duplicates handled if any), our current window s[left...right] is guaranteed to be unique.
- The length of this current unique window is right - left + 1.
- Update max_length = max(max_length, right - left + 1).
Return:
- After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters. Return max_length.

Let's walk through s = "abcabcbb":

`right`	`s[right]`	`char_set` (before add)	Duplicate?	Actions (if duplicate)	`char_set` (after add)	`left`	Current Length (`right - left + 1`)	`max_length`
0	'a'	{}	No	-	{'a'}	0	1	1
1	'b'	{'a'}	No	-	{'a', 'b'}	0	2	2
2	'c'	{'a', 'b'}	No	-	{'a', 'b', 'c'}	0	3	3
3	'a'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=1`	{'b', 'c', 'a'}	1	3 (`3 - 1 + 1`)	3
4	'b'	{'b', 'c', 'a'}	Yes	`char_set.remove('b')`, `left=2`	{'c', 'a', 'b'}	2	3 (`4 - 2 + 1`)	3
5	'c'	{'c', 'a', 'b'}	Yes	`char_set.remove('c')`, `left=3`	{'a', 'b', 'c'}	3	3 (`5 - 3 + 1`)	3
6	'b'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=4`	{'b', 'c', 'b'}	4	3 (`6 - 4 + 1`)	3
				`char_set.remove('b')`, `left=5`	{'c', 'b'}	5	2 (`6 - 5 + 1`)	3

Final max_length is 3. This trace confirms the logic!

Code: Bringing it to life with Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # A set to keep track of characters in the current window
        char_set = set()

        # Left pointer of the sliding window
        left = 0

        # Variable to store the maximum length found so far
        max_length = 0

        # Right pointer iterates through the string
        for right in range(len(s)):
            # If the character at 'right' is already in our set,
            # it means we have a duplicate within the current window.
            # We need to shrink the window from the 'left' until the duplicate is removed.
            while s[right] in char_set:
                char_set.remove(s[left]) # Remove the character at 'left' from the set
                left += 1                # Move the 'left' pointer one step to the right

            # Now that the current character s[right] is guaranteed to be unique
            # in the window [left...right-1], we can add it to our set.
            char_set.add(s[right])

            # Update the maximum length found.
            # The current window length is (right - left + 1).
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

Time Complexity: O(N)
- Both the left and right pointers traverse the string s at most once.
- The right pointer moves N times.
- The left pointer also moves at most N times across all iterations of the outer loop.
- Set operations (add, remove, check in) take O(1) average time.
- Therefore, the total time complexity is linear, O(N), where N is the length of the string s.
Space Complexity: O(min(M, N))
- We use a char_set to store unique characters within the window.
- In the worst case, if all characters in the string are unique (e.g., "abcdefg"), the set will store N characters.
- However, if the character set is limited (e.g., lowercase English letters, M=26), the set will store at most M characters.
- So, the space complexity is bounded by the smaller of the string's length N and the size of the character set M.

Key Takeaways

Sliding Window Technique: This problem is a prime example of the "sliding window" pattern, which is incredibly useful for array/string problems involving a contiguous subsegment. It helps optimize solutions from O(N^2) (e.g., checking every possible substring) to O(N).
Set for Uniqueness Checks: Using a hash set (set in Python) is crucial for efficient O(1) average-time lookups, insertions, and deletions, which allows the sliding window to perform optimally.
Two Pointers (Left and Right): The left pointer helps shrink the window when a condition is violated (duplicate found), while the right pointer expands it.

Keep practicing, and you'll master these patterns in no time! Happy coding!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 23:08:20

DEV Community