Maximize cost of removing all occurrences of substrings “ab” and “ba”

  

import java.util.*;

  

class GFG {

  

    

    

    public static int MaxCollection(

        String S, int P, int Q)

    {

        

        

        char maxstr[]

            = (P >= Q ? "ab" : "ba").toCharArray();

  

        

        

        char minstr[]

            = (P >= Q ? "ba" : "ab").toCharArray();

  

        

        int maxp = Math.max(P, Q);

  

        

        int minp = Math.min(P, Q);

  

        

        int cost = 0;

  

        

        

  

        

        Stack<Character> stack1 = new Stack<>();

        char[] s = S.toCharArray();

  

        

        for (char ch : s) {

  

            

  

            if (!stack1.isEmpty()

                && (stack1.peek() == maxstr[0]

                    && ch == maxstr[1])) {

  

                

                stack1.pop();

  

                

                cost += maxp;

            }

  

            

            else {

  

                stack1.push(ch);

            }

        }

  

        

        StringBuilder sb = new StringBuilder();

  

        

        while (!stack1.isEmpty())

            sb.append(stack1.pop());

  

        

        

        sb = sb.reverse();

        String remstr = sb.toString();

  

        

        for (char ch : remstr.toCharArray()) {

  

            

            if (!stack1.isEmpty()

                && (stack1.peek() == minstr[0]

                    && ch == minstr[1])) {

  

                

                stack1.pop();

  

                

                cost += minp;

            }

  

            

            else {

                stack1.push(ch);

            }

        }

  

        

        return cost;

    }

  

    

    public static void main(String[] args)

    {

  

        

        String S = "cbbaabbaab";

  

        

        int P = 6;

        int Q = 4;

  

        System.out.println(MaxCollection(S, P, Q));

    }

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets