Question

How to find the longest substring without repeating characters in PHP

Answer 1

/*
 * Finds the longest substring without repeating characters.
 * This version keeps a presence table and shrinks the window
 * by clearing characters until the duplicate is removed.
 *
 * Time complexity: O(n)
 */
function longestUniqueSubstringASCII(string $s): string
{
    $seen = array_fill(0, 256, false);

    $left = 0;
    $right = 0;
    $bestLeft = 0;
    $bestRight = 0;

    $n = strlen($s);

    while ($right < $n) {
        $c = ord($s[$right]);

        if ($seen[$c]) {
            // Shrink window until we remove the duplicate
            while ($s[$left] !== $s[$right]) {
                $seen[ord($s[$left])] = false;
                $left++;
            }
            $left++; // skip the duplicate itself
        } else {
            $seen[$c] = true;

            if ($right - $left > $bestRight - $bestLeft) {
                $bestLeft = $left;
                $bestRight = $right;
            }
        }

        $right++;
    }

    return substr($s, $bestLeft, $bestRight - $bestLeft + 1);
}

$str = "xwwwqfwwxqwyq";
$result = longestUniqueSubstringASCII($str);

echo "Input: $str\n";
echo "Longest substring without repeating characters: $result\n";



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals

Answer 2

/*
 * Finds the longest substring without repeating characters.
 * Uses a sliding window and a table of last-seen indexes.
 *
 * - $lastSeen[c] stores the most recent index of character c.
 * - $left/$right define the current window.
 * - When a duplicate appears inside the window, move $left forward.
 *
 * Time complexity: O(n)
 */
function longestUniqueSubstring(string $s): string
{
    $lastSeen = array_fill(0, 256, -1);

    $left = 0;
    $bestStart = 0;
    $bestLength = 0;

    $n = strlen($s);

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

        // If character was seen inside the current window, move left
        if ($lastSeen[$c] >= $left) {
            $left = $lastSeen[$c] + 1;
        }

        // Update last-seen index
        $lastSeen[$c] = $right;

        // Check if this window is the best so far
        $windowLength = $right - $left + 1;
        if ($windowLength > $bestLength) {
            $bestLength = $windowLength;
            $bestStart = $left;
        }
    }

    return substr($s, $bestStart, $bestLength);
}

$str = "xwwwqfwwxqwyq";
$result = longestUniqueSubstring($str);

echo "Input: $str\n";
echo "Longest substring without repeating characters: $result\n";



/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals