LeetCode 3: Longest Substring Without Repeating Characters

LeetCode Problem 3, Longest Substring Without Repeating Characters, is a popular coding interview question that helps developers understand strings, Hash Maps, and the Sliding Window technique.

In this tutorial, we will solve the problem using PHP, understand the brute-force approach, optimize it using Sliding Window, and walk through the solution with detailed examples and a dry run.

1. Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

A substring is a continuous sequence of characters within a string. Every character in the required substring must be unique.

Example 1

s = "abcabcbb"

Output: 3

Explanation: The longest substring without repeating characters is "abc", which has a length of 3. Other valid answers include "bca" and "cab".

Example 2

s = "bbbbb"

Output: 1

Explanation: Every character is the same, so the longest valid substring is "b", with a length of 1.

Example 3

s = "pwwkew"

Output: 3

Explanation: The longest valid substring can be "wke" or "kew", both with a length of 3. Note that "pwke" is not a substring because its characters are not consecutive.

2. Understanding Substrings

A substring is a sequence of characters that appear consecutively in the original string.

This difference is important. The problem asks for a substring, which means we cannot skip any characters between the beginning and end of the selected range.

3. Brute Force Approach

The brute-force approach checks all possible substrings and finds the longest one that contains no duplicate characters.

For every starting index, we expand the substring character by character. We store encountered characters in a temporary array. If a duplicate appears, we stop expanding from that starting point.

PHP Code – Brute Force

class Solution {
    function lengthOfLongestSubstring($s) {
        $n = strlen($s);
        $maxLength = 0;

        for ($i = 0; $i < $n; $i++) {
            $seen = [];

            for ($j = $i; $j < $n; $j++) {
                $char = $s[$j];

                if (isset($seen[$char])) {
                    break;
                }

                $seen[$char] = true;

                $length = $j - $i + 1;
                $maxLength = max($maxLength, $length);
            }
        }

        return $maxLength;
    }
}

How the Brute Force Approach Works

Consider the input "abcabcbb".

• Start at index 0 and form "a", "ab", and "abc". Stop when another "a" appears.
• Start at index 1 and form "b", "bc", and "bca". Stop when "b" repeats.
• Continue from the remaining starting positions and update the maximum valid length.

4. Optimized Approach – Sliding Window

The Sliding Window technique maintains a continuous range of characters and adjusts that range as we traverse the string. Instead of restarting the search for every character, we move two pointers through the string.

• Left pointer: The starting index of the current window.
• Right pointer: The ending index of the current window.
• Hash Map: Stores the most recent index of each character.

When a repeated character is found inside the current window, we move the left pointer to one position after its previous occurrence.

Sliding Window Visualization

5. Step-by-Step Algorithm

1. Initialize left = 0 and maxLength = 0.
2. Create an empty Hash Map named lastSeen to store the last index of each character.
3. Traverse the string using the right pointer.
4. For each character, check if it exists in the Hash Map and if its previous index is inside the current window.
5. If a duplicate is inside the window, move left to the index after that previous occurrence.
6. Update the character’s latest index in the Hash Map.
7. Calculate the current window length and update maxLength.
8. Return maxLength after processing the string.

6. Complete Optimized PHP Solution

The following solution uses Sliding Window and a Hash Map to achieve linear time complexity.

class Solution {
    function lengthOfLongestSubstring($s) {
        $lastSeen = [];
        $left = 0;
        $maxLength = 0;
        $n = strlen($s);

        for ($right = 0; $right < $n; $right++) {
            $char = $s[$right];

            if (isset($lastSeen[$char]) &&
                $lastSeen[$char] >= $left) {
                $left = $lastSeen[$char] + 1;
            }

            $lastSeen[$char] = $right;

            $currentLength = $right - $left + 1;

            $maxLength = max(
                $maxLength,
                $currentLength
            );
        }

        return $maxLength;
    }
}

7. Explaining the Code Line by Line

Step 1: Initialize Variables

$lastSeen = [];
$left = 0;
$maxLength = 0;
$n = strlen($s);

$lastSeen stores the most recent position of each character. $left marks the start of the current window, and $maxLength stores the longest valid substring length found so far.

Step 2: Traverse the String

for ($right = 0; $right < $n; $right++) {
    $char = $s[$right];
}

The right pointer moves through the string one character at a time, identifying the current character.

Step 3: Check for Repeated Characters

if (isset($lastSeen[$char]) &&
    $lastSeen[$char] >= $left) {
    $left = $lastSeen[$char] + 1;
}

This is the most important part of the algorithm.

• isset() checks whether the character has been encountered before.
• $lastSeen[$char] >= $left confirms that the previous occurrence lies inside the current window.
• $left = $lastSeen[$char] + 1 moves the left pointer beyond the previous occurrence.

Step 4: Update the Hash Map

$lastSeen[$char] = $right;

We store the current index as the latest position of the character. This makes future duplicate checks accurate.

Step 5: Calculate the Window Length

$currentLength = $right - $left + 1;
$maxLength = max($maxLength, $currentLength);

The current window length is calculated by subtracting the left index from the right index and adding 1. We then update the maximum length if the current window is longer.

Step 6: Return the Result

return $maxLength;

After the loop has processed all characters, the maximum length is the answer.

8. Detailed Dry Run

Let’s execute the optimized code with the input "abcabcbb".

Understanding the Important Iterations

Iteration 1: The first character is a at index 0. The current window is "a", so the maximum length is 1.

Iteration 2: The character b is new. The current window becomes "ab", with a length of 2.

Iteration 3: The character c is also new. The window becomes "abc", and the maximum length becomes 3.

Iteration 4: The character a repeats at index 3. Its previous index was 0, so we move left to 1. The current window becomes "bca".

Iteration 5: The character b repeats at index 4. Its previous index was 1, so we move left to 2. The window becomes "cab".

Iteration 6: The character c repeats. Its previous index was 2, so we move left to 3. The window becomes "abc".

Iteration 7: The character b repeats at index 6. Its previous index was 4, so we move left to 5. The window becomes "cb".

Iteration 8: The character b repeats again. Its previous index is 6, so we move left to 7. The window becomes "b".

9. Why Do We Check lastSeen[char] >= left?

This condition prevents the left pointer from moving backwards when a character repeats outside the current window.

Consider the string "abba".

At index 3, the previous occurrence of a was at index 0, but the current window starts at index 2. Since index 0 is outside the current window, we must not move the left pointer backwards.

10. Edge Cases

11. Time and Space Complexity

Time Complexity: O(n)

The right pointer traverses the string once. The left pointer only moves forward, so each character is processed a constant number of times. Therefore, the optimized solution has linear time complexity.

Space Complexity: O(min(n, k))

The Hash Map stores the latest index of each distinct character. Here, n is the string length and k is the size of the possible character set. For the problem’s ASCII character set, the Hash Map has a bounded number of entries.

12. Common Mistakes to Avoid

• Confusing substring and subsequence: A substring must contain consecutive characters.
• Moving the left pointer backwards: Check that the previous occurrence is at or beyond the current left pointer.
• Not using the latest occurrence: Store the most recent index of each character.
• Updating maximum length too early: Adjust the window first, then calculate its length.
• Using unnecessary nested loops: Sliding Window is more efficient for this problem.

13. Frequently Asked Questions

14. Conclusion

LeetCode 3: Longest Substring Without Repeating Characters is an important coding interview problem for learning the Sliding Window technique and Hash Maps.

The brute-force approach helps us understand how substrings work, but the optimized Sliding Window approach eliminates repeated work by maintaining a valid range of unique characters.

Understanding this pattern will help you solve many other string and array problems commonly asked in technical interviews.