Scale Engineer

Maximum Score From Removing Substrings

Med
#1573Time: O(N^2) or worse. In the worst case, we might perform O(N) removals, and each removal involves a string search and modification, which takes O(N) time.Space: O(N), where N is the length of the string. A new string or `StringBuilder` is often created in each step of removal.1 company
Patterns
Greedy
Data structures
StringStack
Companies
Swiggy

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It repeatedly scans the string to find and remove occurrences of "ab" or "ba", adding the corresponding points to a running total. The choice of which substring to remove at each step is made greedily based on which one offers more points.

Algorithm

  1. Initialize totalScore = 0.
  2. Start a loop that continues as long as removals are possible.
  3. Inside the loop, set a flag found = false.
  4. Determine which pair to prioritize. If x > y, prioritize "ab". Otherwise, prioritize "ba".
  5. Search for the high-priority pair (e.g., using s.indexOf("ab")).
  6. If found, remove it from the string, add its score to totalScore, set found = true, and continue to the next iteration of the loop.
  7. If the high-priority pair is not found, search for the low-priority pair.
  8. If the low-priority pair is found, remove it, add its score, set found = true, and continue.
  9. If neither pair is found (found remains false), break the loop.
  10. Return totalScore.

Walkthrough

The brute-force method involves iterating through the string in a loop. In each iteration, we search for the substrings "ab" and "ba". Based on the scores x and y, we decide which one to remove first. For instance, if x is greater than y, we prioritize finding and removing "ab". After a removal, the string is modified, and the process repeats from the beginning of the new, shorter string. This continues until no more "ab" or "ba" substrings can be found. While simple to conceptualize, this method is very slow because string search and modification operations inside a loop lead to a high time complexity.

Complexity

Time

O(N^2) or worse. In the worst case, we might perform O(N) removals, and each removal involves a string search and modification, which takes O(N) time.

Space

O(N), where N is the length of the string. A new string or `StringBuilder` is often created in each step of removal.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Extremely inefficient due to repeated string searching and manipulation.

  • Each removal operation on a string is costly, typically O(N).

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {public  int maximumGain(String s, int x, int y) {    if (x < y) {      return maximumGain(new StringBuilder(s).reverse().toString(), y, x);    }    int ans = 0;    Deque<Character> stk1 = new ArrayDeque<>();    Deque<Character> stk2 = new ArrayDeque<>();    for (char c : s.toCharArray()) {      if (c != 'b') {        stk1.push(c);      } else {        if (!stk1.isEmpty() && stk1.peek() == 'a') {          stk1.pop();          ans += x;        } else {          stk1.push(c);        }      }    }    while (!stk1.isEmpty()) {      char c = stk1.pop();      if (c != 'b') {        stk2.push(c);      } else {        if (!stk2.isEmpty() && stk2.peek() == 'a') {          stk2.pop();          ans += y;        } else {          stk2.push(c);        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem