Maximum Score From Removing Substrings - Video Solutions

Problem Overview: You are given a string s and two scores x and y. Removing substring "ab" earns x points and removing "ba" earns y points. After each removal the string closes the gap, potentially creating new substrings. The goal is to maximize the total score.

Approach 1: Greedy Approach with Stack (O(n) time, O(n) space)

The key observation: always remove the higher scoring substring first. If x > y, remove "ab" first; otherwise remove "ba". Scan the string and simulate removals using a stack. When the current character forms the target pair with the stack top, pop the stack and add the corresponding score. Otherwise push the character. After the first pass, run the same process on the remaining characters to remove the other substring type. This greedy ordering ensures higher-value removals happen before they get blocked by lower-value ones. Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(n) for the stack.

This method relies on greedy decision making and local pair elimination. It appears frequently in stack and greedy interview problems where removing patterns affects future structure.

Approach 2: Two-Pointer Counting Strategy (O(n) time, O(1) space)

You can simulate the same greedy logic without an explicit stack by counting characters while scanning. Process the higher-value substring first. Maintain counters for the first and second characters in the pair. When a matching pair forms, increment the score and decrement the counter instead of storing characters. Characters that cannot form the preferred pair are carried forward and used when processing the second substring type. This approach mimics stack behavior using counters and avoids storing the entire intermediate string.

The scan still touches each character a constant number of times, giving O(n) time complexity with O(1) extra space. This is a good choice when memory constraints matter or when implementing in performance-sensitive environments.

The problem primarily tests understanding of greedy ordering in string manipulation. Removing the wrong pair first can destroy opportunities for higher scoring pairs later.

Recommended for interviews: The greedy stack approach is the most expected solution. It clearly demonstrates why removing the higher-value substring first maximizes the score and is easy to reason about during discussion. The two-pointer version is a space-optimized refinement that strong candidates may mention after presenting the stack-based solution.