Blogger Hommie

Posted on May 31

LeetCode Solution: 3. Longest Substring Without Repeating Characters

#leetcode #dsa #programming #tutorial

3. Longest Substring Without Repeating Characters 🟡 Medium

Hey Dev.to fam! 👋 Today, we're diving into a LeetCode classic that’s a fantastic introduction to a super common and powerful algorithm pattern: the Sliding Window. This problem, "Longest Substring Without Repeating Characters," is a must-know for anyone looking to sharpen their algorithmic skills. It might seem tricky at first, but once you grasp the core idea, it opens doors to solving many similar problems!

2. Problem Explanation

Imagine you have a string of characters, like "abcabcbb". Your goal is to find the longest possible piece of that string (a substring) where every character in that piece is unique. No repeats allowed!

Let's break down the examples:

Example 1: s = "abcabcbb"
- "abc" is a substring with no repeating characters. Its length is 3.
- "bca" and "cab" are also valid substrings of length 3.
- Can we do better? "abca" has 'a' repeated. "abcab" has 'a' and 'b' repeated.
- So, the longest is 3.
Example 2: s = "bbbbb"
- Any substring longer than "b" will have repeating 'b's.
- The longest substring without repeats is "b", with a length of 1.
Example 3: s = "pwwkew"
- "pw" -> length 2
- "pww" -> 'w' repeats. Not valid.
- "wke" -> length 3.
- "kew" -> length 3.
- "pwke" is NOT a substring, it's a subsequence (characters not contiguous). We're strictly looking for substrings.
- The longest is 3 (e.g., "wke").

Constraints to keep in mind:

The string s can be empty (0 length) up to 5 * 10^4 characters long.
It can contain English letters, digits, symbols, and spaces. This means we're dealing with a diverse set of characters, but their total possible count (e.g., ASCII range) is manageable.

3. Intuition

How would you try to solve this manually? You'd probably start checking substrings:
"a" (len 1)
"ab" (len 2)
"abc" (len 3)
"abca" - oh no, 'a' repeats!
So, "abc" was the longest for that segment. What now? Do you start fresh from "b"?
"b" (len 1)
"bc" (len 2)
"bca" (len 3)
"bcab" - 'b' repeats!

This "try, fail, reset" approach hints at something: when we hit a repeat, we don't necessarily need to throw away everything we've built. We just need to remove the problematic part.

This "expanding a window and shrinking it when things go wrong" is the core idea behind the Sliding Window technique. We'll maintain a "window" of characters and try to expand it as much as possible. If we encounter a duplicate, we'll shrink the window from the other end until the duplicate is gone.

To efficiently check for duplicates within our current window, a HashSet (or unordered_set in C++) is perfect because it allows for lightning-fast (average O(1) time) checks and removals.

4. Approach

We'll use two pointers, left and right, to define our "sliding window" s[left...right].
We'll also use an unordered_set<char> (let's call it charSet) to keep track of unique characters currently within our window.

Here's the step-by-step approach:

Initialize:
- left = 0: This pointer marks the beginning of our current substring.
- maxLength = 0: This will store the maximum length found so far.
- charSet = {}: An empty set to store characters in the current window.
Iterate with right pointer:
- Loop right from 0 to s.length() - 1. The right pointer expands our window to the right.
Handle Duplicates (Shrink the Window):
- Inside the loop, before adding s[right] to our charSet, we check: while (charSet.find(s[right]) != charSet.end())
  - This while loop runs only if s[right] is ALREADY present in our charSet. This means s[right] is a duplicate within our current window s[left...right-1].
  - To remove the duplicate, we need to shrink the window from the left. We do this by:
    - Removing s[left] from charSet.
    - Incrementing left (left++).
  - This while loop continues until s[right] is no longer a duplicate in the newly shrunk window.
Add New Character (Expand the Window):
- Once the while loop finishes (meaning s[right] is now unique in the window s[left...right-1]), we can safely add s[right] to charSet: charSet.insert(s[right]).
Update Maximum Length:
- After s[right] is added, our current valid substring without repeating characters is s[left...right].
- Its length is right - left + 1.
- Update maxLength: maxLength = max(maxLength, right - left + 1).
Return maxLength: After the right pointer has traversed the entire string, maxLength will hold the length of the longest substring without repeating characters.

Let's quickly trace s = "abcabcbb":

`right`	`s[right]`	`charSet` (before add)	`while` loop action	`charSet` (after add)	`left`	`curr_len` (`r-l+1`)	`maxLength`	Current Window (for clarity)
0	'a'	{}	-	{'a'}	0	1	1	"a"
1	'b'	{'a'}	-	{'a', 'b'}	0	2	2	"ab"
2	'c'	{'a', 'b'}	-	{'a', 'b', 'c'}	0	3	3	"abc"
3	'a'	{'a', 'b', 'c'}	`erase('a')`, `l=1`	{'b', 'c', 'a'}	1	3	3	"bca"
4	'b'	{'b', 'c', 'a'}	`erase('b')`, `l=2`	{'c', 'a', 'b'}	2	3	3	"cab"
5	'c'	{'c', 'a', 'b'}	`erase('c')`, `l=3`	{'a', 'b', 'c'}	3	3	3	"abc"
6	'b'	{'a', 'b', 'c'}	`erase('a')`, `l=4`
			`erase('b')`, `l=5`	{'c', 'b'}	5	2	3	"cb"
7	'b'	{'c', 'b'}	`erase('c')`, `l=6`
			`erase('b')`, `l=7`	{'b'}	7	1	3	"b"

Final maxLength is 3. Perfect!

5. Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int maxLength = 0;
        // An unordered_set is perfect for quickly checking for duplicates
        // and storing unique characters in our current window.
        unordered_set<char> charSet;

        // The 'right' pointer expands our window
        for (int right = 0; right < s.length(); right++) {
            // If the character at 'right' is already in our set,
            // it means we have a duplicate within our current window.
            // We need to shrink the window from the 'left' until the duplicate is removed.
            while (charSet.find(s[right]) != charSet.end()) {
                charSet.erase(s[left]); // Remove the character at 'left'
                left++;                 // Move 'left' pointer forward
            }

            // Once the character at 'right' is unique in the window,
            // add it to our set.
            charSet.insert(s[right]);

            // Update the maximum length found so far.
            // Current window length is (right - left + 1).
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;       
    }
};

6. Time & Space Complexity Analysis

Time Complexity: O(N)

The right pointer iterates through the string s exactly once, performing N increments.
The left pointer also moves forward at most N times in total over the entire execution. Each character is added to the charSet once (by right) and removed from the charSet at most once (by left).
unordered_set operations (insert, find, erase) take average O(1) time. In the worst case (due to hash collisions), they can degrade to O(N), but for character sets (like ASCII), collisions are rare enough that the average case holds true.
Since both pointers traverse the string at most once, and set operations are constant time on average, the total time complexity is O(N), where N is the length of the string s.

Space Complexity: O(min(N, M)) or O(1)

The charSet stores unique characters present in the current sliding window.
In the worst case, all characters in s might be unique, so the set could potentially store up to N characters.
However, the problem constraints state that s consists of English letters, digits, symbols, and spaces. This means the total number of possible unique characters (let's call it M) is limited (e.g., ASCII has 128 or 256 characters).
Therefore, the maximum size of charSet is bounded by min(N, M). Since M (e.g., 128 for ASCII) is a constant, we often simplify the space complexity to O(1) in competitive programming contexts, implying constant extra space relative to the input size N.

7. Key Takeaways

Sliding Window Pattern: This problem is a quintessential example of the "Sliding Window" technique. It's incredibly useful for problems involving subarrays or substrings where you need to find something (max, min, count) within a contiguous range.
Two Pointers (left, right): The left and right pointers define the current window. right expands the window, and left contracts it when a condition (like uniqueness) is violated.
unordered_set for Uniqueness Checks: An unordered_set (or HashSet in other languages) is your best friend for quickly checking if an element exists and maintaining a collection of unique items. Its average O(1) time complexity for insert, find, and erase is crucial for optimizing the sliding window.
Understanding while vs. if: The while loop for shrinking the window (while (charSet.find(s[right]) != charSet.end())) is critical. It ensures that all instances of the duplicate character (and any characters preceding it) are removed from the left until s[right] is truly unique in the current window. An if here would only remove one character and might leave other duplicates, leading to incorrect results.

8. Submission Details

Author Account: ahB1IK4YXF
Publishing Time: 2026-05-31 22:54:05

DEV Community