Remove all occurrences of substrings from a string

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


Category: Data Structure And Algorithms Tags: C#

Remove all occurrences of substrings from a string - Code Files

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
Last modified on 27 October 2022
Nikhil Joshi

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

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x