Skip to main content
Talentd

Maximum Score From Removing Substrings - Solution & Explanation

MediumStringStackGreedy33 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

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 substring "ab" and gain x points.
    • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
  • Remove substring "ba" and gain y points.
    • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

 

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- 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

 

Constraints:

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

Approach Overview

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.

Approach 1: Greedy Approach with Stack

In this approach, we prioritize removing the substring with a higher score first. We utilize a stack to efficiently traverse and remove substrings from the string. Given two substrings 'ab' and 'ba', and their scores x and y, we decide which to remove first based on the higher score. The stack helps in processing the string in a single pass, adding character by character and checking for the target substring ending each time.

This solution leverages a stack to remove 'ab' or 'ba' substrings based on their point values. The approach consists of two sweeps across the input string: one for the highest point substring and another for the remaining to maximize the score.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack used in substring removal.

Try this approach in the editor →

Approach 2: Two-Pointer Approach

The Two-Pointer approach leverages two pointers to parse through the string and eliminate substrings optimally. By managing two scanning points, determining which pattern to remove can be executed with minimal operations, optimizing score calculation effectively.

This C solution uses two pointers combined with a simulated stack to efficiently parse and optimize substring removal by maximizing the scores at each step through linear traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to stack arrays used to manage character tracking.

Try this approach in the editor →

Approach 3: 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.

Next, we only need to consider the case where the string contains only "a" and "b". If the string contains other characters, we can treat them as split points, dividing the string into several substrings that contain only "a" and "b", and then calculate the score for each substring separately.

We observe that for a substring containing only "a" and "b", no matter what operations we take, we will eventually be left with only one type of character, or an empty string. Since each operation removes one "a" and one "b" simultaneously, the total number of operations is fixed. We can greedily remove "ab" first, then remove "ba", which ensures the maximum score.

Therefore, we can use two variables cnt1 and cnt2 to record the counts of "a" and "b" respectively, then traverse the string and update cnt1 and cnt2 according to different cases of the current character, while calculating the score.

For the current character c being traversed:

  • If c is "a", since we want to remove "ab" first, we don't eliminate this character at this time, only increment cnt1;
  • If c is "b", if cnt1 > 0 at this time, we can eliminate one "ab" and add x points; otherwise, we can only increment cnt2;
  • If c is another character, then for this substring, we have cnt2 "b"s and cnt1 "a"s left. We can eliminate min(cnt1, cnt2) "ba"s and add several y points.

After traversal, we need to handle the remaining "ba"s and add several y points.

The time complexity is O(n), where n is the length of string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Stack

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack used in substring removal.

Two-Pointer Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to stack arrays used to manage character tracking.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with StackO(n)O(n)Best general solution. Easy to implement and explain during interviews.
Two-Pointer CountingO(n)O(1)When minimizing memory usage or avoiding auxiliary stack storage.

Video Solution

Maximum Score From Removing Substrings | 2 Approaches | With Proof | Leetcode 1717 • codestorywithMIK • 17,136 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score From Removing Substrings easy or hard?
Maximum Score From Removing Substrings is rated Medium difficulty on LeetCode. The implementation is straightforward once the greedy insight is recognized, but identifying that the higher scoring substring must be removed first is the key challenge.
Maximum Score From Removing Substrings Python/Java solution
Implement the greedy strategy: remove the higher-value substring first using a stack or counters, then process the remaining string for the other pair. The same logic works across Python, Java, C++, JavaScript, and C# with linear time complexity.
How to solve Maximum Score From Removing Substrings in O(n)?
Use a greedy strategy. Determine which substring ('ab' or 'ba') gives higher points and remove it first while scanning the string using a stack or counters. After finishing the first pass, process the remaining characters to remove the other substring type. This guarantees maximum score in linear time.
What is the best approach for Maximum Score From Removing Substrings?
The greedy approach with a stack is the most common solution. Always remove the higher scoring substring first ('ab' or 'ba'), then process the remaining string for the other pair. Each character is processed once, giving O(n) time complexity and O(n) space for the stack.
Is Maximum Score From Removing Substrings asked at Google/Amazon/Meta?
Greedy string manipulation and stack-based pattern removal problems frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of greedy ordering and efficient string processing in O(n) time.
What data structure is used in Maximum Score From Removing Substrings?
The most common solution uses a stack to track characters while scanning the string. The stack helps detect when the current character forms a removable pair with the previous one. An optimized approach can replace the stack with simple counters and two-pointer style scanning.
What is the time complexity of Maximum Score From Removing Substrings?
The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed and popped from the stack at most once or processed once in the two-pointer version. Space complexity is O(n) with a stack or O(1) using the counting approach.

Ready to solve this problem?

Practice Maximum Score From Removing Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Words Obtained After Adding a Letter