#1717

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Maximum Score From Removing Substrings

Compute the highest score by greedily removing specific substrings using a stack to track state transitions efficiently.

string stack greedy

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 an "ab" substring to earn x points, or remove a "ba" substring to earn y points. Each removal deletes the substring and the remaining string closes together. Your goal is to maximize the total points obtainable by removing substrings optimally.

Return an integer representing the maximum score after performing the operations. For example, given s = "cdbcbbaaabab", x = 4, y = 5, the optimal sequence of removals produces a score of 19 by carefully prioritizing higher-scoring substrings first while using stack-based tracking to avoid missing removable patterns.

Examples

Example 1

Input: s = "cdbcbbaaabab", x = 4, y = 5

Output: 19

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

Example details omitted.

Constraints

1 <= s.length <= 105
1 <= x, y <= 104
s consists of lowercase English letters.

Solution Approach

Prioritize the Higher-Value Substring

Compare x and y and always remove the substring with the higher point value first. This ensures that each removal contributes maximally to the score before lower-value substrings interfere with potential matches.

Use a Stack to Track Characters

Iterate through the string and push characters onto a stack. When the top of the stack forms a removable substring with the current character, pop the stack and add points. This approach efficiently handles overlapping patterns without rescanning processed parts.

Alternate Removal for Remaining Substrings

After removing all instances of the higher-value substring, process the remaining string for the other substring type. Using a second pass with the same stack strategy guarantees that no valid removal opportunities are missed.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Each character is pushed and popped at most once, giving O(n) time complexity. Stack storage only requires O(1) extra space relative to input as removals reduce the working string.

What Interviewers Usually Probe

Expect candidates to identify the greedy priority for substring removal.
Look for stack-based state management instead of repeated string replacements.
Watch for handling overlapping substrings efficiently.

Common Pitfalls or Variants

Common pitfalls

Removing substrings in the wrong order reduces the maximum achievable score.
Using repeated string scanning instead of a stack leads to O(n^2) runtime.
Failing to handle overlapping patterns causes missed removals.

Follow-up variants

Consider the case where multiple substring types exist with different point values and overlapping occurrences.
Modify the problem to handle longer patterns like "abc" and "cba" with distinct scores.
Handle streaming input where characters arrive sequentially, requiring online stack-based processing.

FAQ

How does stack-based state management apply in Maximum Score From Removing Substrings?

A stack tracks the current string state, allowing immediate detection of removable 'ab' or 'ba' substrings without rescanning, ensuring greedy choices are applied efficiently.

What is the time complexity of the optimal solution?

The algorithm runs in O(n) time since each character is processed once and popped from the stack at most once.

Can the algorithm handle overlapping substrings?

Yes, the stack approach correctly handles overlaps by immediately removing any detected substring and continuing with remaining characters.

Which substring should be removed first?

Always remove the substring with the higher point value first to maximize the total score.

What happens if x equals y?

Either removal order yields the same total score, but maintaining stack-based tracking still ensures correct handling of overlapping patterns.

terminal

Solution

Solution 1: Greedy

We can assume that the score of substring "ab" is always no less than the score of substring "ba". If not, we can swap "a" and "b", and simultaneously swap $x$ and $y$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        a, b = "a", "b"
        if x < y:
            x, y = y, x
            a, b = b, a
        ans = cnt1 = cnt2 = 0
        for c in s:
            if c == a:
                cnt1 += 1
            elif c == b:
                if cnt1:
                    ans += x
                    cnt1 -= 1
                else:
                    cnt2 += 1
            else:
                ans += min(cnt1, cnt2) * y
                cnt1 = cnt2 = 0
        ans += min(cnt1, cnt2) * y
        return ans

Continue Practicing

#1541 minimum insertions to balance a parentheses string #1963 minimum number of swaps to make the string balanced #2030 smallest k length subsequence with occurrences of a letter