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.
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:-
T = “codigninjaishandledbyninjasandninjadothis”
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 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).
Also check out - Substr C++
85+ registered