⚡Flashcard Drill➔
NeetCode #806LC-1717MediumGreedy
← Back to All Problems

#806 · #1717 · Maximum Score From Removing Substrings(删除子字符串的最大得分)

📌 Problem Statement & Constraints

You are given a string s and two integers x and y. You may remove the substring ab for x points or ba for y points, any number of times. Return the maximum score. Constraints: 1 <= s.length <= 10^5, 1 <= x, y <= 10^4.

💡 Core Algorithmic Approaches

  1. Always remove the more valuable pair first: doing so can never reduce the total, because a greedy stack removal of the higher pair is optimal.
  2. Use a stack: scan the string and whenever the top of the stack plus the current character form the target pair, pop and score.
  3. The stack removal is exactly the greedy that captures every non-overlapping occurrence of the pair.
  4. After removing all of the first pair, run the same procedure on the remaining characters for the other pair.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def remove_pair(text: str, first: str, second: str, score: int):
            total = 0
            stack = []
            for c in text:
                if stack and stack[-1] == first and c == second:
                    stack.pop()        # remove the pair
                    total += score
                else:
                    stack.append(c)
            return total, "".join(stack)

        if x >= y:
            pts, rest = remove_pair(s, "a", "b", x)
            pts2, _ = remove_pair(rest, "b", "a", y)
        else:
            pts, rest = remove_pair(s, "b", "a", y)
            pts2, _ = remove_pair(rest, "a", "b", x)
        return pts + pts2

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear stack passes.
💾 Space Complexity
O(n): the stack and the reduced string.

⚠️ Interview Pitfalls & Follow-ups

  • Removing the cheaper pair first: that can block a more valuable removal, so the higher-value pair must go first.
  • Using str.replace repeatedly: it is correct but can be O(n^2) on adversarial input; the stack is linear.
  • Forgetting to continue on the remaining string: after the first pass the other pair may still be present.
  • Comparing x >= y with the wrong branch: the branch must match the pair actually removed first.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems