Remove All Occurrences of a Substring - Practice Coding Problems

Remove All Occurrences of a Substring - Problem

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Input & Output

Example 1 — Basic Removal

$ Input: s = "daabcbaabcbc", part = "abc"

› Output: "dab"

💡 Note: Remove first "abc" → "daabcbbc", then remove second "abc" → "dabb", then remove "bbc" doesn't contain "abc", final result is "dab"

Example 2 — Complete Removal

$ Input: s = "aabababa", part = "aba"

› Output: "ba"

💡 Note: Remove "aba" from position 1 → "ababa", remove "aba" from position 0 → "ba", no more occurrences found

Example 3 — No Occurrences

$ Input: s = "hello", part = "world"

› Output: "hello"

💡 Note: The substring "world" is not found in "hello", so the original string is returned unchanged

Constraints

1 ≤ s.length ≤ 1000
1 ≤ part.length ≤ 1000
s and part consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with target substring to remove

Process

Remove occurrences, which may expose new ones

Output

Final string with all occurrences removed

Key Takeaway

🎯 Key Insight: Each removal might expose new pattern occurrences, requiring continuous checking until no more matches exist

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is that removing one occurrence of a substring might create new occurrences. The optimal approach uses a stack-based method to process characters one by one, checking for pattern matches at the end of the stack. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use a stack to build the result, removing characters when the pattern is detected
Brute Force - Repeated Find and Remove	O(n²)	O(n)	Repeatedly find the leftmost occurrence of part and remove it until no more occurrences exist

Stack-Based Approach — Algorithm Steps

Step 1: Iterate through each character in the string
Step 2: Add character to stack
Step 3: Check if last 'part.length' characters in stack form the pattern
Step 4: If yes, remove those characters from stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Add to Stack

Push each character onto stack

Check Pattern

When stack end matches pattern, remove it

Continue

Process remaining characters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, char* part) {
    int sLen = strlen(s);
    int partLen = strlen(part);
    char* stack = (char*)malloc((sLen + 1) * sizeof(char));
    int stackSize = 0;
    
    for (int i = 0; i < sLen; i++) {
        stack[stackSize++] = s[i];
        if (stackSize >= partLen && 
            strncmp(stack + stackSize - partLen, part, partLen) == 0) {
            stackSize -= partLen;
        }
    }
    
    stack[stackSize] = '\0';
    return stack;
}

int main() {
    char s[1001], part[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(part, sizeof(part), stdin);
    part[strcspn(part, "\n")] = 0;
    
    char* result = solution(s, part);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

We iterate through the string once, and each character is pushed and popped at most once from the stack.

✓ Linear Growth

Space Complexity

O(n)

In worst case, the stack can contain all characters of the input string when no pattern matches are found.

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler