# Maximize cost obtained by removal of substrings “pr” or “rp” from a given String

**Introduction**

In this article, we will discuss the problem of maximizing the cost obtained by removing substring “pr” and “rp” from a given string. Such trivial problems have been asked in a few competitive coding platforms.

**Problem Statement**

Given a string **s **and two integers **X **and **Y**. Your task is the find the maximum cost required to remove all the substrings of the form “pr” or “rp”. The removal of “pr” takes X cost, and the removal of “rp” takes Y cost.

**Example**

**Sample_Input**

String s = “prprprrp”

X = 7

Y = 10

**Required_Output**

37

**Approach and Explanation**

The solution code provided in this article is in C++. To solve this problem, we shall be using concepts of Greedy Programming. Readers with no prior knowledge of the same can learn more about the topic from __Greedy Algorithms__.

To solve the given problem, we can follow these steps:

- For each string, we will check if X>Y. If true, then we remove the substring “pr”. Else if Y>X, we remove the substring “rp”.

- So, in our function, the first check we do is whether Y>X. If true, then we swap all the p’s with r’s and r’s with p’s. We also swap the values of X and Y.

- Then we declare three variables-
**maxCost**(int),**count_p**(int), and**count_r**(int). All three are initialized to zero. The**maxCost**variable will store the maximum cost that occurred. The**count_p**and**count_r**will keep track of all the p’s and r’s after the removal of “pr” respectively, from the given string.

- We iterate through the string and check for p’s and r’s. This is done by maintaining a stack where for each ‘p’ one ‘r’ is popped.

- Once a ‘p’ is encountered, increase
**count_p**by one.

- If we encounter ‘r’ we check for the value of
**count_p.**If**count_p**is not zero then, decrease**count_p**by one and calculate**maxCost**by**maxCost+=X**. Else increase**count_r**by one.

- If we encounter neither of them, we update the
**maxCost**by doing**maxCost += min(count_p, count_r) * Y**. In the end, we return this**maxCost**which is our required answer.

**C++ implementation**

```
#include <bits/stdc++.h>
using namespace std;
int pr_string(string s,int X,int Y){
int size=s.length();
if(Y>X){
for(int i=0;i<size;i++){
if(s[i]=='p')s[i]='r';
else if(s[i]=='r')s[i]='p';
}
swap(X,Y);
}
int maxCost=0;
int count_p=0;
int count_r=0;
for(int i=0;i<size;i++){
if(s[i]=='p') count_p++;
else if(s[i]=='r'){
if(count_p>0) { count_p--; maxCost+=X; }
else count_r++;
}
else{
maxCost+=min(count_p,count_r)*Y;
count_p=0;
count_r=0;
}
}
maxCost+=min(count_p,count_r)*Y;
return maxCost;
}
int main(){
cout<<pr_string("abppprrr",5,4)<<endl;
cout<<pr_string("prprprrp",7,10)<<endl;
cout<<pr_string("abcdpqrpqr",3,4)<<endl;
return 0;
}
```

OUTPUT

```
15
37
4
```

**Complexities**

**Time Complexity**

We traverse the whole input string once to find the “pr” or “rp” in the given solution code. Thus, the time complexity is,

**T(n) = O(N)**

**Space Complexity**

In the given solution code, no extra space is used by the code. Thus,

**Space Complexity = O(1)**

**Frequently Asked Questions**

**What are the other ways of solving this problem?**

We can solve this problem in two more ways. One is recursion, where we recursively call our function to find “pr” or “rp” and then find the max cost. The other way is using Dynamic Programming.

**Are such problems important?**

Yes, the problems such as this one discussed in this article are important as they help us in understanding the basic concepts of__Stack__,__Greedy Algorithms__, and much more. These concepts are important for building a good foundation in the DSA paradigm.

**Key Takeaways**

To summarize the article, we discussed the problem- maximizing cost obtained by removing substring “pr” or “rp” from a given string. We saw the problem statement, an example, and an approach. We also saw the solution code for the approach along with the time and space complexities.

Improve your coding skills by practising various problems of various difficulty levels on our __CodeStudio__.

Learn about various topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more from our __CN Library | Free Online Coding Resources__.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think