Maximize cost of repeated removal of string P or its reverse from the string S

0 0 9 minutes read

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 amount
int ans[1] = {0};
 
// Function to remove reverse of P first
void 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 first
void 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 answer
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
int 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 approach
import 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 first
def 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 first
def 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 answer
def 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 S
S = "12333444"
 
# Given X and Y
x = 5
y = 4
 
# Given P
P = "34"
 
# Function Call
print(solve(S, x, y, P[0], P[1]))

C#

// C# program for the above approach
using 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 first
function 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 first
function 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 answer
function 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 S
let S = "12333444"
 
// Given X and Y
let x = 5
let y = 4
 
// Given P
let P = "34"
 
// Function Call
document.write(solve(S, x, y, P[0], P[1]))
 
// This code is contributed by _saurabh_jaiswal.
</script>

Output:

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