Given two positive integers X and Y and two numeric strings S and P of length N and 2 respectively, the task is to find the maximum total cost obtained by repeatedly removing string P or the reverse of the string P from the string S at the cost of X and Y respectively.
Examples:
Input: S = “12333444”, X = 5, Y = 4, P = “34”
Output: 15
Explanation:
Below are the operations to remove substring to get the maximum cost:
- Remove the string “34″ from the string S. Therefore, the string S modifies to “123344”. Cost = 5.
- Remove the string “34″ from the string S. Therefore, the string S modifies to “1234”. Cost = 5.
- Remove the string “34″ from the string S. Therefore, the string S modifies to “12”. Cost = 5.
Therefore, the total cost is 5 + 5 + 5 = 15.
Input: S = “12121221”, X = 7, Y = 10, P = “12”
Output: 37
Approach: The given problem can be solved using the Greedy Approach and Stack. Follow the steps below to solve the problem:
- Initialize a variable, say ans as 0 to store the maximum cost of removing the given substrings.
- Initialize a Stack that is used to decide whether the string P or the reverse of P is removed.
- Traverse the given string S and perform the following steps:
- If the current character and the top character are not equal to P[1] and P[0] respectively or if the stack is empty, then push the current character in the Stack.
- Otherwise, remove the top element of the stack and increment the value ans by X.
- Similarly, the reverse of the string P can be removed from any string by adding Y to the cost.
- Now, If X is greater than Y, then removing P before removing the reverse of P will give a greater value. Otherwise, remove the reverse of the pattern P first.
- After completing the above steps, print the value of ans as the total maximum cost.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Initialize amountint ans[1] = {0};// Function to remove reverse of P firstvoid rp(string str, int x, int y, bool flag, char p, char r){ // Initialize empty stack stack<char>stk; // Iterate through each char in string for(int i = 0; i < str.length(); i++) { // Remove reverse of P if (str[i]== p) { if (stk.size() > 0 && stk.top() == r) { ans[0] += y; // Pop the element from // the stack stk.pop(); } else { stk.push(str[i]); } } else { stk.push(str[i]); } // Remove P, if needed ans[0]+=1; if (flag) { string s = ""; stack<char> s1 ; while (s1.size() > 0) { s += s1.top(); s1.pop(); } pr(s, x, y, false, p, r); } }}// Function to remove the string P firstvoid pr(string str, int x, int y, bool flag, char p, char r) { // Initialize empty stack stack<int>stk; // Iterate through each char // in string for(int i = 0; i < str.length(); i++) { // Remove the string P if (str[i]== r) { if (stk.size() > 0 && stk.top() == p) { ans[0] += x; stk.pop(); } // If no such pair exists just // push the chars to stack else { stk.push(str[i]); } } else { stk.push(str[i]); } ans[0] += 1; // Remove reverse of P, if needed if (flag) { string s = ""; stack<char>s1; while (s1.size() > 0) { s = s + s1.top(); s1.pop(); } rp(s, x, y, false, p, r); } }}// Function to find the appropriate answerint solve(string str, int x, int y, char p, char r) { // Remove P then reverse of P if (x > y) pr(str, x, y, true, p, r); // Remove reverse of P then P else rp(str, x, y, true, p, r); // Return the result return ans[0]-1;}// Driver Codeint main() { // Given string S string S = "12333444"; // Given X and Y int x = 5; int y = 4; // Given P String P = "34"; // Function Call cout<<solve(S, x, y, P[0], P[1]<<endl; return 0; } // This code is contributed by dwivediyash |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Initialize amount static int[] ans = {0}; // Function to remove the string P first static void pr(String str, int x, int y, boolean flag, char p, char r) { // Initialize empty stack Stack<Character> stack = new Stack<Character>(); // Iterate through each char // in string for(int i = 0; i < str.length(); i++) { // Remove the string P if (str.charAt(i) == r) { if (stack.size() > 0 && stack.peek() == p) { ans[0] += x; stack.pop(); } // If no such pair exists just // push the chars to stack else { stack.push(str.charAt(i)); } } else { stack.push(str.charAt(i)); } ans[0] += 1; // Remove reverse of P, if needed if (flag) { String s = ""; Stack<Character> s1 = stack; while (s1.size() > 0) { s = s + s1.peek(); s1.pop(); } rp(s, x, y, false, p, r); } } } // Function to remove reverse of P first static void rp(String str, int x, int y, boolean flag, char p, char r) { // Initialize empty stack Stack<Character> stack = new Stack<Character>(); // Iterate through each char in string for(int i = 0; i < str.length(); i++) { // Remove reverse of P if (str.charAt(i) == p) { if (stack.size() > 0 && stack.peek() == r) { ans[0] += y; // Pop the element from // the stack stack.pop(); } else { stack.push(str.charAt(i)); } } else { stack.push(str.charAt(i)); } // Remove P, if needed ans[0]+=1; if (flag) { String s = ""; Stack<Character> s1 = stack; while (s1.size() > 0) { s = s + s1.peek(); s1.pop(); } pr(s, x, y, false, p, r); } } } // Function to find the appropriate answer static int solve(String str, int x, int y, char p, char r) { // Remove P then reverse of P if (x > y) pr(str, x, y, true, p, r); // Remove reverse of P then P else rp(str, x, y, true, p, r); // Return the result return ans[0]-1; } // Driver code public static void main(String[] args) { // Given string S String S = "12333444"; // Given X and Y int x = 5; int y = 4; // Given P String P = "34"; // Function Call System.out.print(solve(S, x, y, P.charAt(0), P.charAt(1))); }}// This code is contributed by mukesh07. |
Python3
# Python program for the above approach# Function to remove reverse of P firstdef rp(string, x, y, ans, flag, p, r): # Initialize empty stack stack = [] # Iterate through each char in string for char in string: # Remove reverse of P if char == p: if stack and stack[-1] == r: ans[0] += y # Pop the element from # the stack stack.pop() else: stack.append(char) else: stack.append(char) # Remove P, if needed if flag: pr("".join(stack), x, y, ans, False, p, r)# Function to remove the string P firstdef pr(string, x, y, ans, flag, p, r): # Initialize empty stack stack = [] # Iterate through each char # in string for char in string: # Remove the string P if char == r: if stack and stack[-1] == p: ans[0] += x stack.pop() # If no such pair exists just # push the chars to stack else: stack.append(char) else: stack.append(char) # Remove reverse of P, if needed if flag: rp("".join(stack), x, y, ans, False, p, r)# Function to find the appropriate answerdef solve(string, x, y, p, r): # Initialize amount ans = [0] # Remove P then reverse of P if x > y: pr(string, x, y, ans, True, p, r) # Remove reverse of P then P else: rp(string, x, y, ans, True, p, r) # Return the result return ans[0]# Driver Code# Given string SS = "12333444"# Given X and Yx = 5y = 4# Given PP = "34"# Function Callprint(solve(S, x, y, P[0], P[1])) |
C#
// C# program for the above approachusing System;using System.Collections;class GFG { // Initialize amount static int[] ans = {0}; // Function to remove the string P first static void pr(string str, int x, int y, bool flag, char p, char r) { // Initialize empty stack Stack stack = new Stack(); // Iterate through each char // in string foreach(char c in str) { // Remove the string P if (c == r) { if (stack.Count > 0 && (char)stack.Peek() == p) { ans[0] += x; stack.Pop(); } // If no such pair exists just // push the chars to stack else { stack.Push(c); } } else { stack.Push(c); } ans[0]+=1; // Remove reverse of P, if needed if (flag) { string s = ""; Stack s1 = stack; while (s1.Count > 0) { s = s + (char)s1.Peek(); s1.Pop(); } rp(s, x, y, false, p, r); } } } // Function to remove reverse of P first static void rp(string str, int x, int y, bool flag, char p, char r) { // Initialize empty stack Stack stack = new Stack(); // Iterate through each char in string foreach(char c in str) { // Remove reverse of P if (c == p) { if (stack.Count > 0 && (char)stack.Peek() == r) { ans[0] += y; // Pop the element from // the stack stack.Pop(); } else { stack.Push(c); } } else { stack.Push(c); } // Remove P, if needed ans[0]+=1; if (flag) { string s = ""; Stack s1 = stack; while (s1.Count > 0) { s = s + (char)s1.Peek(); s1.Pop(); } pr(s, x, y, false, p, r); } } } // Function to find the appropriate answer static int solve(string str, int x, int y, char p, char r) { // Remove P then reverse of P if (x > y) pr(str, x, y, true, p, r); // Remove reverse of P then P else rp(str, x, y, true, p, r); // Return the result return ans[0]-1; } static void Main() { // Given string S string S = "12333444"; // Given X and Y int x = 5; int y = 4; // Given P string P = "34"; // Function Call Console.Write(solve(S, x, y, P[0], P[1])); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Function to remove reverse of P firstfunction rp(string, x, y, ans, flag, p, r) { // Initialize empty stack let stack = [] // Iterate through each char in string for (let char of string) { // Remove reverse of P if (char == p) { if (stack && stack[stack.length - 1] == r) { ans[0] += y // Pop the element from // the stack stack.pop() } else stack.push(char) } else stack.push(char) // Remove P, if needed if (flag) { pr(stack.join(""), x, y, ans, false, p, r) } }}// Function to remove the string P firstfunction pr(string, x, y, ans, flag, p, r) { // Initialize empty stack let stack = [] // Iterate through each char // in string for (let char of string) { // Remove the string P if (char == r) { if (stack && stack[stack.length - 1] == p) { ans[0] += x stack.pop() } // If no such pair exists just // push the chars to stack else { stack.push(char) } } else { stack.push(char) } // Remove reverse of P, if needed if (flag) { rp(stack.join(""), x, y, ans, false, p, r) } }}// Function to find the appropriate answerfunction solve(string, x, y, p, r) { // Initialize amount let ans = [0] // Remove P then reverse of P if (x > y) pr(string, x, y, ans, true, p, r) // Remove reverse of P then P else rp(string, x, y, ans, true, p, r) // Return the result return ans[0]}// Driver Code// Given string Slet S = "12333444"// Given X and Ylet x = 5let y = 4// Given Plet P = "34"// Function Calldocument.write(solve(S, x, y, P[0], P[1]))// This code is contributed by _saurabh_jaiswal.</script> |
Output:
15
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
