Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach and Explanation
5.
C++ implementation
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

Recommended problems -

 

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

 

Happy Coding!

 

Previous article
Greedy Algorithm in Graph Theory
Next article
Minimize insertions or deletions to make the frequency of each array element equal to its value
Live masterclass