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.