1717. Maximum Score From Removing Substrings LeetCode Solution

In this guide, you will get 1717. Maximum Score From Removing Substrings LeetCode Solution with the best time and space complexity. The solution to Maximum Score From Removing Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Score From Removing Substrings solution in C++
4. Maximum Score From Removing Substrings solution in Java
5. Maximum Score From Removing Substrings solution in Python
6. Additional Resources

Problem Statement of Maximum Score From Removing Substrings

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.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

1717. Maximum Score From Removing Substrings LeetCode Solution in C++

class Solution {
 public:
  int maximumGain(string s, int x, int y) {
    // The assumption that gain("ab") > gain("ba") while removing "ba" first is
    // optimal is contradicted. Only "b(ab)a" satisfies the condition of
    // preventing two "ba" removals, but after removing "ab", we can still
    // remove one "ba", resulting in a higher gain. Thus, removing "ba" first is
    // not optimal.
    return x > y ? gain(s, "ab", x, "ba", y) : gain(s, "ba", y, "ab", x);
  }

 private:
  // Returns the points gained by first removing sub1 ("ab" | "ba") from s with
  // point1, then removing sub2 ("ab" | "ba") from s with point2.
  int gain(const string& s, const string& sub1, int point1, const string& sub2,
           int point2) {
    int points = 0;
    vector<char> stack1;
    vector<char> stack2;

    // Remove "sub1" from s with point1 gain.
    for (const char c : s)
      if (!stack1.empty() && stack1.back() == sub1[0] && c == sub1[1]) {
        stack1.pop_back();
        points += point1;
      } else {
        stack1.push_back(c);
      }

    // Remove "sub2" from s with point2 gain.
    for (const char c : stack1)
      if (!stack2.empty() && stack2.back() == sub2[0] && c == sub2[1]) {
        stack2.pop_back();
        points += point2;
      } else {
        stack2.push_back(c);
      }

    return points;
  }
};
/* code provided by PROGIEZ */

1717. Maximum Score From Removing Substrings LeetCode Solution in Java

class Solution {
  public int maximumGain(String s, int x, int y) {
    // The assumption that gain("ab") > gain("ba") while removing "ba" first is
    // optimal is contradicted. Only "b(ab)a" satisfies the condition of
    // preventing two "ba" removals, but after removing "ab", we can still
    // remove one "ba", resulting in a higher gain. Thus, removing "ba" first is
    // not optimal.
    return x > y ? gain(s, "ab", x, "ba", y) : gain(s, "ba", y, "ab", x);
  }

  // Returns the points gained by first removing sub1 ("ab" | "ba") from s with
  // point1, then removing sub2 ("ab" | "ba") from s with point2.
  private int gain(final String s, final String sub1, int point1, final String sub2, int point2) {
    int points = 0;
    Stack<Character> stack1 = new Stack<>();
    Stack<Character> stack2 = new Stack<>();

    // Remove "sub1" from s with point1 gain.
    for (final char c : s.toCharArray())
      if (!stack1.isEmpty() && stack1.peek() == sub1.charAt(0) && c == sub1.charAt(1)) {
        stack1.pop();
        points += point1;
      } else {
        stack1.push(c);
      }

    // Remove "sub2" from s with point2 gain.
    for (final char c : stack1)
      if (!stack2.isEmpty() && stack2.peek() == sub2.charAt(0) && c == sub2.charAt(1)) {
        stack2.pop();
        points += point2;
      } else {
        stack2.push(c);
      }

    return points;
  }
}
// code provided by PROGIEZ

1717. Maximum Score From Removing Substrings LeetCode Solution in Python

class Solution:
  def maximumGain(self, s: str, x: int, y: int) -> int:
    # The assumption that gain('ab') > gain('ba') while removing 'ba' first is
    # optimal is contradicted. Only 'b(ab)a' satisfies the condition of
    # preventing two 'ba' removals, but after removing 'ab', we can still
    # remove one 'ba', resulting in a higher gain. Thus, removing 'ba' first is
    # not optimal.
    return (self._gain(s, 'ab', x, 'ba', y) if x > y else
            self._gain(s, 'ba', y, 'ab', x))

  # Returns the points gained by first removing sub1 ('ab' | 'ba') from s with
  # point1, then removing sub2 ('ab' | 'ba') from s with point2.
  def _gain(self, s: str, sub1: str, point1: int, sub2: str, point2: int) -> int:
    points = 0
    stack1 = []
    stack2 = []

    # Remove 'sub1' from s with point1 gain.
    for c in s:
      if stack1 and stack1[-1] == sub1[0] and c == sub1[1]:
        stack1.pop()
        points += point1
      else:
        stack1.append(c)

    # Remove 'sub2' from s with point2 gain.
    for c in stack1:
      if stack2 and stack2[-1] == sub2[0] and c == sub2[1]:
        stack2.pop()
        points += point2
      else:
        stack2.append(c)

    return points
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.