Watch 10 video solutions for Maximum Score From Removing Substrings, a medium level problem involving String, Stack, Greedy. This walkthrough by NeetCodeIO has 13,809 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
"ab" and gain x points.
"ab" from "cabxbae" it becomes "cxbae"."ba" and gain y points.
"ba" from "cabxbae" it becomes "cabxe".Return the maximum points you can gain after applying the above operations on s.
Example 1:
Input: s = "cdbcbbaaabab", x = 4, y = 5 Output: 19 Explanation: - Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score. - Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score. - Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score. - Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score. Total score = 5 + 4 + 5 + 5 = 19.
Example 2:
Input: s = "aabbaaxybbaabb", x = 5, y = 4 Output: 20
Constraints:
1 <= s.length <= 1051 <= x, y <= 104s consists of lowercase English letters.