1.
Introduction
2.
Approach
2.1.
Algorithm
2.2.
C++ Solution
2.3.
Complexity Analysis
3.
3.1.
How is stack initialized in the above code?
3.2.
What is STL?
3.3.
What are the functions of stack STL?
4.
Conclusion
Last Updated: Mar 27, 2024

# Minimize a String By Removing All Occurrences of Another String

Harsh Goyal
0 upvote

## Introduction

This blog will discuss the various approaches to solve the Minimize a string by removing all occurrences of another string problem. Before jumping into the problem to Minimize a string by removing all occurrences of another string, let’s first understand a String,

The string is a data type, a collection of characters, or a sequence of characters.

Also see, Data Structures

In this Minimize a string by removing all occurrences of another string problem, we need to remove all the occurrences of a string ‘x’ from the string ‘t’, and, we need to return the size of the resultant length of the string ‘t’.

For Example:-

x = “ninja”

Output:- 26

## Approach

The Solution considers traversing the complete string ‘t’ and we will use stack to solve this minimizes a string by removing all occurrences of another string problem. In this, we will push the current character while traversing and if the size of that stack is greater or equal to ‘v’, then, in that case, we will check if the top ‘v’ characters of the stack become equals to the string ‘x’ or not, in this case, if they are equal then we need to return those characters from the string ‘t’. After the completion of the whole iteration, we need to return the size of the stack, which will be our minimum length of string ‘t’ after removing all the occurrences of string ‘x’ from string ‘t’.

### Algorithm

Step 1. Create a function ‘getResult()’ that will accept 4 parameters which are as follows:-

• String ‘t’
• ‘A’ - size of string ‘t’
• String ‘x’
• ‘B’ - size of string ‘x’

Step 2. Initialize a stack of character type ‘sq’.

Step 3. Make an iteration using the ‘for’ loop with the help of a variable ‘i’ which will iterate from 0 to ‘A’.

Step 4. Push each character of the string ‘t’ in ‘sq’.

Step 5. Check if the size of the stack is greater than or equal to ‘B’, then initialize an empty string ‘temp’ and make an iteration using ‘for’ loop with the help of a variable ‘k’ which will iterate from ‘A - 1’ to 0. In this loop

• If character on ‘kth’ index in string ‘x’ is not equal to top element of the stack then initialize a variable ‘temp2’ and iterate using ‘while’ loop and push each character on ‘temp2th’ index of ‘temp’ and increment the count of ‘temp2’. After completion of the while loop , break the function using ‘break’
• Else concatenate character on the top of the stack ‘sq’ with ‘temp’ and then pop the top element from the stack ‘sq’.

Step 6. Return the size of the stack ‘sq’.

### C++ Solution

#include <bits/stdc++.h>
using namespace std;

int getResult(string t, int A,string x, int B)
{

// Initialize stack of characters
stack<char> sq;

for (int i = 0; i < A; i++)
{

// Push character of the 't' string in stack
sq.push(t[i]);

if (sq.size() >= B)
{
string temp = "";

// Traverse the string K in reverse
for (int k = B - 1; k >= 0; k--)
{
if (x[k] != sq.top())
{
int temp2 = 0;
while (temp2 != temp.size())
{
sq.push(temp[temp2]);
temp2++;
}

break;
}

// Store the string
else
{

temp = sq.top() + temp;

// Remove the top element of the stack
sq.pop();
}
}
}
}

// Stack size will be the size of the resultant string
return sq.size();
}

// Driver Code
int main()
{
string x = "ninja";

int A = t.length();
int B = x.length();

cout << "Size before removing all the occurrences of another string is:- " << A << endl;

// Function Call
cout << "Minimum size after removing all the occurrences of another string is:- ";

cout << getResult(t, A, x, B) << endl;
}

Output:

Output :

Size before removing all the occurrences of another string is:- 41

Minimum size after removing all the occurrences of another string is:- 26

### Complexity Analysis

Time Complexity: O(A * B)

Incall to ‘getResult()’, As we are traversing the whole string ‘t’ and while traversing we are checking for the string ‘x’ using a nested loop, therefore, the overall time complexity is O(A * B) where ‘A’ and ‘B’ are the size of string ‘t’ and ‘x’ respectively.

Space Complexity: O(A)

As we are using a stack that will store a maximum of ‘A’ characters, therefore, the overall space complexity will be O(A).

Also check out - Substr C++

### How is stack initialized in the above code?

Stack is initialized using the STL in c++.

### What is STL?

Standard Template Library is known as STL, and it is a set of template classes of C++ which provide us the functionality of different data structures.

### What are the functions of stack STL?

There are five major functions of stack STL, which are as follows:-

• Push
• Pop
• Size
• Empty
• Top

## Conclusion

In this article, we discussed the problem Minimize a string by removing all occurrences of another string, discussed the various approaches to solving this problem programmatically, the time and space complexities,
Check out this problem - Longest String Chain