Minimize A String By Removing All Occurrences Of Another String

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. 

For more information on the string, refer to this link.

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:-

T = “codigninjaishandledbyninjasandninjadothis”

x = “ninja”

Output:- 26

Approach 

The Solution considers traversing the complete string ‘t’ and we will use stack to solve this minimize 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 t = "codigninjaishandledbyninjasandninjadothis";
	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).

Frequently asked questions

1) How is stack initialized in the above code?

Ans. Stack is initialized using the STL in c++.

 

2) What is STL?

Ans. 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. 

 

3) What are the functions of stack STL?

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

  • Push
  • Pop
  • Size
  • Empty
  • Top

Key takeaways

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, 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think