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
- 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.
- Use a stack: scan the string and whenever the top of the stack plus the current character form the target pair, pop and score.
- The stack removal is exactly the greedy that captures every non-overlapping occurrence of the pair.
- 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.replacerepeatedly: 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 >= ywith 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.