Remove All Occurrences of a Substring

Medium
400.

Remove All Occurrences of a Substring

Remove All Occurrences of a Substring is a medium coding problem on strings, simulation and stack, asked in Amazon, Adobe and Twitter interviews.

Given two strings s and part, repeatedly remove the leftmost occurrence of part from s until s no longer contains it, then return s.

Example 1

Input
s = "daabcbaabcbc", part = "abc"
Output
dab

Example 2

Input
s = "axxxxyyyyb", part = "xy"
Output
ab

Example 3

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

Constraints

  • 1 <= s.length <= 40
  • 1 <= part.length <= 4
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} part
 * @return {string}
 */
var removeOccurrences = function(s, part) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove All Occurrences of a Substring — Problem & Solution

Remove All Occurrences of a Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove All Occurrences of a Substring is a medium coding problem on strings, simulation and stack, asked in Amazon, Adobe and Twitter interviews.

  • Difficulty: Medium
  • Topics: Strings, Simulation, Stack
  • Asked at: Amazon, Adobe, Twitter
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s and part, repeatedly remove the leftmost occurrence of part from s until s no longer contains it, then return s.

Example 1

Input: s = "daabcbaabcbc", part = "abc"
Output: dab

Example 2

Input: s = "axxxxyyyyb", part = "xy"
Output: ab

Example 3

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

Constraints

  • 1 <= s.length <= 40
  • 1 <= part.length <= 4
  • Both consist of lowercase English letters.

Hints for Remove All Occurrences of a Substring

  1. Hint 1

    Push characters onto a stack one at a time.

  2. Hint 2

    After each push, check whether the top part.length characters spell part.

  3. Hint 3

    If they do, pop them off — this handles matches that only appear after an earlier removal.

How to solve Remove All Occurrences of a Substring

Push characters onto a stack and, after each push, delete the top |part| characters if they spell part.

Approach

  1. For each ch, push it; if the stack's tail equals part, remove it.

Why it works

Removing the leftmost occurrence first is equivalent to removing each occurrence as soon as it is completed, and the stack detects occurrences that only appear after an earlier removal.

Complexity

  • Time — O(n · m)
  • Space — O(n)

Pitfalls

  • Repeatedly calling replace is simpler but quadratic in the number of removals.

Reference solution

Python

def removeOccurrences(s: str, part: str) -> str:
    stack = []
    m = len(part)
    for ch in s:
        stack.append(ch)
        if len(stack) >= m and "".join(stack[-m:]) == part:
            del stack[-m:]
    return "".join(stack)

Java

public static String removeOccurrences(String s, String part) {
    StringBuilder stack = new StringBuilder();
    int m = part.length();
    for (int i = 0; i < s.length(); i++) {
        stack.append(s.charAt(i));
        if (stack.length() >= m) {
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (stack.charAt(stack.length() - m + j) != part.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) stack.setLength(stack.length() - m);
        }
    }
    return stack.toString();
}

C++

string removeOccurrences(string s, string part) {
    string stk;
    int m = (int) part.size();
    for (char c : s) {
        stk.push_back(c);
        if ((int) stk.size() >= m && stk.compare(stk.size() - m, m, part) == 0) {
            stk.erase(stk.size() - m);
        }
    }
    return stk;
}

JavaScript

var removeOccurrences = function(s, part) {
    const stack = [];
    const m = part.length;
    for (let i = 0; i < s.length; i++) {
        stack.push(s.charAt(i));
        if (stack.length >= m) {
            let match = true;
            for (let j = 0; j < m; j++) {
                if (stack[stack.length - m + j] !== part.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) stack.length -= m;
        }
    }
    return stack.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure