Maximum Score From Removing Substrings

MEDIUM

Description

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 <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Maximum Score From Removing Substrings. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation

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

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

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 Analysis

Time Complexity: 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 Complexity: O(N), where N is the length of the string. A new string or `StringBuilder` is often created in each step of removal.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Maximum Score From Removing Substrings. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Score From Removing Substrings

Patterns:

Greedy

Data Structures:

StringStack

Companies:

Swiggy |