Understanding the Longest Substring Without Repeating Characters Algorithm

Problem Overview

Find the length of the longest substring without repeating characters in a given string.

Function Signature

/**
 * @param String $s
 * @return Integer
 */
function lengthOfLongestSubstring($s)

Algorithm Breakdown

Initial Setup

The function begins by initializing several key variables:

$length = strlen($s);     // Get total length of input string
$maxLength = 0;           // Track the maximum substring length found
$charIndexMap = [];       // Hash map to store character positions
$left = 0;                // Left side of sliding window

The Sliding Window Technique

The "sliding window" technique uses two variables to maintain a window of characters:

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

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

    $charIndexMap[$char] = $right;
    $maxLength = max($maxLength, $right - $left + 1);
}

How It Works

1. $right iterates through the string character by character
2. For each character:
   • If we've seen it before within our current window, move $left
   • Update the character's position in our map
   • Calculate the current window size and update maximum length if necessary

Example Walkthrough

Using the input string "abcabcbb":

1. "a" -> maxLength = 1
2. "ab" -> maxLength = 2
3. "abc" -> maxLength = 3
4. "abca": We hit second "a":
   • Find previous "a" at index 0
   • Move $left to index 1
   • Current window becomes "bca"
   • maxLength stays 3
5. Continue...

Final result: 3 (the substring "abc")

Complexity Analysis

• Time Complexity: O(n) where n is the length of the string
• Space Complexity: O(n) probably

The sliding window technique demonstrated here is particularly efficient as it only requires a single pass through the string while maintaining optimal space complexity.