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

Aditya Narayan Joardar
Last Updated: May 13, 2022

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 and two integers 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

  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 StackGreedy 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!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think