Show problems as
Classic problem #1910MediumStringStackSimulation

Remove All Occurrences of a Substring

Real-world version: Cut the Marker from the Tape
Tracked in this browser only
Read Remove All Occurrences of a Substring on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A label machine has printed a long paper tape carrying the lowercase letters of s, one letter per cell, and the operator has to strip a faulty marker part out of it.

The operator repeats one step for as long as the marker still appears anywhere on the tape:

  1. Find the leftmost run of cells whose letters spell part, that is the match beginning at the smallest cell index.
  2. Cut those cells out and splice the two loose ends of the tape together.

Splicing can bring letters together that were far apart before, and the marker may well turn up across a fresh splice, in which case it is cut too. The operator stops only when no run of cells anywhere on the tape spells part.

Return the letters left on the tape when the operator stops, as a string. The result may be the empty string.

Examples

Example 1

Input
s = "aabb", part = "ab"
Output
""

The leftmost match sits at cells 1 and 2. Cutting it splices the remaining `a` and `b` together, and that pair spells the marker as well, so it goes too and nothing is left.

Example 2

Input
s = "pqrpqqrpqr", part = "pqr"
Output
"pqqr"

The leftmost match is at the start. Cutting it leaves `pqqrpqr`, whose leftmost match is the final three cells, and cutting that leaves `pqqr`, which holds no match.

Example 3

Input
s = "abc", part = "d"
Output
"abc"

No cell spells the marker, so the operator makes no cut and the tape is unchanged.

Example 4

Input
s = "ababa", part = "aba"
Output
"ba"

Two runs spell the marker, one starting at cell 0 and one at cell 2, and they share cells. The operator takes the one starting at cell 0, leaving `ba`, which holds no match.

Example 5

Input
s = "aaa", part = "aa"
Output
"a"

The leftmost match covers cells 0 and 1, and cutting it leaves a single `a`.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= part.length <= 1000
  • s and part consist of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_occurrences(s: str, part: str) -> str:
Java
public String removeOccurrences(String s, String part)

More on the same topics