595. Score by Removing Pairs
A puzzle game shows a string s of lowercase letters. On each move you may delete two adjacent letters if they spell "ab", which earns x points, or if they spell "ba", which earns y points. After a deletion the letters on both sides become neighbours, so new pairs can appear. You may make as many moves as you like, in any order, and you may stop at any time.
Return the maximum total number of points that can be earned. Letters other than a and b can never be deleted and act as walls that separate the string. Your solution should run in O(n) time with O(n) extra space.
Example 1
- Input:
- s = "cabbac", x = 5, y = 3
- Output:
- 8
- Explanation:
Remove "ab" for 5 to get "cbac", then remove "ba" for 3 to get "cc", a total of 8.
Example 2
- Input:
- s = "aabbaa", x = 4, y = 6
- Output:
- 12
- Explanation:
Since "ba" is worth more, remove it twice (the middle pair, then the pair that appears) for 12 and end with "aa".
Example 3
- Input:
- s = "bbbb", x = 7, y = 9
- Output:
- 0
- Explanation:
There is no letter a, so no pair can be removed and the score is 0.
Constraints
1 ≤ s.length ≤ 2000001 ≤ x, y ≤ 104sconsists of lowercase English letters only.- The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)