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

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;
}

You can also try this code with Online C++ Compiler

Run Code

OUTPUT

15
37
4

Also check out - Substr C++

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

1. 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.
    
2. 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 Coding Ninjas Studio.

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

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

Happy Coding!