1910. Remove All Occurrences of a Substring: Optimization

[rfool]

Subsequent calls to strpos could use lastpos-partlen+1 as an offset.

[mah-shamim]

Optimized Solution using str_replace()

<?php
function removeOccurrences($s, $part) {
    while (strpos($s, $part) !== false) {
        $s = str_replace($part, "", $s);
    }
    return $s;
}

// Example Cases
echo removeOccurrences("daabcbaabcbc", "abc") . "\n"; // Output: "dab"
echo removeOccurrences("axxxxyyyyb", "xy") . "\n";    // Output: "ab"
?>

✅ Time Complexity:

• Each str_replace() call scans O(N), and in the worst case (when part appears many times), it can run up to O(N^2).
• However, str_replace() is highly optimized in PHP internals.

✅ Space Complexity:

• O(1) (since PHP modifies strings in place with optimizations).

[mah-shamim]

Manual Efficient Approach using Two Pointers

This approach avoids excessive memory usage caused by multiple string replacements.

<?php
function removeOccurrences($s, $part) {
    $stack = "";
    $partLen = strlen($part);

    for ($i = 0, $n = strlen($s); $i < $n; $i++) {
        $stack .= $s[$i];

        // If the last part matches the substring, remove it
        if (strlen($stack) >= $partLen && substr($stack, -$partLen) === $part) {
            $stack = substr($stack, 0, -$partLen);
        }
    }

    return $stack;
}

// Example Cases
echo removeOccurrences("daabcbaabcbc", "abc") . "\n"; // Output: "dab"
echo removeOccurrences("axxxxyyyyb", "xy") . "\n";    // Output: "ab"
?>

✅ Time Complexity: O(N), as we traverse s once.
✅ Space Complexity: O(N), since we use a dynamic string.