Understanding the Longest Substring Without Repeating Characters Problem in PHP

PHP algorithms strings sliding window hash map leetcode

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.