-1
$\begingroup$

Problem Statement: You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when removing "ab" from "cabxbae" it becomes "cxbae". Remove substring "ba" and gain y points. For example, when removing "ba" from "cabxbae" it becomes "cabxe". Return the maximum points you can gain after applying the above operations on s.

A greedy algorithm solves this problem in O(n). The greedy algorithm works by eliminating all pairs with a higher scoring value before removing pairs of a lower scoring value. Can anyone present a proof for the correctness of a greedy algorithm here. I have been trying, and I cannot convince myself.

$\endgroup$
2
1
$\begingroup$

(For the greedy algorithm described to be optimal, it is also necessary to assume that $x$ and $y$ are nonnegative.)

Without loss of generality, we can assume $y \ge x$.

Suppose to the contrary that the greedy algorithm is not optimal. Then there exist some string (possibly an intermediate state) containing a consecutive pair $\mathrm{ba}$ whose removal is suboptimal. Consider what happens to those letters in the optimal solution.

  • If neither is removed in the optimal solution, then also removing the pair gives a better solution – a contradiction.
  • If exactly one of those letters is removed in the optimal solution, then modifying the solution by first removing the $\mathrm{ba}$ pair, and omitting whatever removal applied to one of them later, gives another solution that is at least as good, contradicting the assumed suboptimality of removing the $\mathrm{ba}$ pair. (Because the other member of the pair was never removed in the optimal solution, this change works, in that it cannot break any later removals.)
  • If both of those letters are removed in the optimal solution, that means they are paired up with an $\mathrm{a}$ on the left and a $\mathrm{b}$ on the right. In this case, we can modify the solution by first removing the $\mathrm{ba}$ pair, and later pairing up and removing those other $\mathrm{a}$ and $\mathrm{b}$, which is again a contradiction.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.