# How to remove all the occurrences of a substring or substrings from a given string

 Category: Data Structure And Algorithms Tags:

## Problem Statement

Let a given string S, remove all the occurrences of sub strings [S1,S2...].

For example S=PAABBCDQ, S1=AB and S2=CD then output should be PQ.

PAABBCDQ Remove AB

PABCDQ Remove AB

PCDQ Remove CD

PQ

## Solution

To solve this we can make use of a stack. We can iterate all the characters from 0 to n (length of string) and every time we encounter a character we can push that in stack. Once a new character is encountered we have to match all the characters to the left with given substring. If all matched then we can remove them from stack. Look into the following code does the same.

```string RemoveAllOccurences(string input, string[] subStrings)
{
Stack<char> stack = new Stack<char>();

for (int i = 0; i < input.Length; i++)
{
// Push everything in the stack
stack.Push(input[i]);
foreach (var subString in subStrings)
{
// Only compare with substring if stack length is equal or grater than substring
if (stack.Count >= subString.Length)
{
// Temp substring to keep track of popped elements
string temp = string.Empty;
for (int j = subString.Length - 1; j >= 0; j--)
{
if (stack.Peek() == subString[j])
{
// If match then pop and keep that in temp
temp = stack.Pop() + temp;
}
else
{
// If not matched then re insert any popped chars in stack
foreach (var c in temp)
{
stack.Push(c);
}
break;
}
}
}
}
}
return GetString(stack);
}

string GetString(Stack<char> stack)
{
string str = "";
while (stack.Count > 0)
{
str = stack.Pop() + str;
}
return str;
}```

Lets run above code

```string str = "PAABBCDQ";
string output = RemoveAllOccurences(str, new string[] { "AB", "CD" });
Console.WriteLine(output);```

Output

PQ

Time complexity: Since we iterate over all the elements of input string and match all the substrings at each iteration complexity will be M(length of string)*N(number of substrings)*O(length of substrings) finally O(M*N*O).

Space complexity: O(N) for stack.

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 164 Questions: 16 Given Best Solutions: 16 *