Leetcode 1717. Maximum Score From Removing Substrings

Problem Explanation

You are given a string s and two integers, x and y. Your task is to remove substrings "ab" (gaining x points) and/or "ba" (gaining y points) and calculate the maximum number of points you can get by performing these operations an unlimited number of times.

Example

Consider the input s = "cdbcbbaaabab", x = 4, and y = 5.

• First, remove "ba" from "cdbcbbaaabab", resulting in "cdbcbbaaab" and gaining 5 points.
• Next, remove "ab" from "cdbcbbaaab", resulting in "cdbcbbaa" and gaining 4 points.
• Then, remove "ba" from "cdbcbbaa", resulting in "cdbcba" and gaining 5 points.
• Finally, remove "ba" from "cdbcba", resulting in "cdbc" and gaining 5 points.

The total score is 5 + 4 + 5 + 5 = 19.

Solution Approach

The solution uses a greedy approach to remove substrings "ab" and "ba" whenever possible, accumulating the score as we go through the string. In each step, we remove one of the substrings and update the score based on the substring's value. To avoid repeating work, we can count the number of "ab" and "ba" substrings that we can remove.

Algorithm Steps

1. Initialize two counters abCount and baCount to count occurrences of substrings "ab" and "ba".
2. Initialize a variable score to store the total score.
3. Iterate through the string and perform the following steps for each character: a. If the current character is 'a', increment abCount. b. If the current character is 'b' and abCount > 0, that means we can remove a "ab" substring (pair previous 'a' with this 'b'), so increment the score by x and decrement the abCount. c. If the current character is 'b', increment baCount. d. If the current character is 'a' and baCount > 0, that means we can remove a "ba" substring (pair previous 'b' with this 'a'), so increment the score by y and decrement the baCount.
4. Return the total score.

Python Solution

1class Solution:
2    def maximumGain(self, s: str, x: int, y: int) -> int:
3        abCount = baCount = score = 0
4        
5        for char in s:
6            if char == 'a':
7                abCount += 1
8            elif char == 'b' and abCount > 0:
9                score += x
10                abCount -= 1
11            
12            if char == 'b':
13                baCount += 1
14            elif char == 'a' and baCount > 0:
15                score += y
16                baCount -= 1
17        
18        return score

Java Solution

1class Solution {
2    public int maximumGain(String s, int x, int y) {
3        int abCount = 0, baCount = 0, score = 0;
4
5        for (char ch : s.toCharArray()) {
6            if (ch == 'a') {
7                abCount++;
8            } else if (ch == 'b' && abCount > 0) {
9                score += x;
10                abCount--;
11            }
12
13            if (ch == 'b') {
14                baCount++;
15            } else if (ch == 'a' && baCount > 0) {
16                score += y;
17                baCount--;
18            }
19        }
20
21        return score;
22    }
23}

JavaScript Solution

1class Solution {
2    maximumGain(s, x, y) {
3        let abCount = 0, baCount = 0, score = 0;
4
5        for (let char of s) {
6            if (char === 'a') {
7                abCount++;
8            } else if (char === 'b' && abCount > 0) {
9                score += x;
10                abCount--;
11            }
12
13            if (char === 'b') {
14                baCount++;
15            } else if (char === 'a' && baCount > 0) {
16                score += y;
17                baCount--;
18            }
19        }
20
21        return score;
22    }
23}

C++ Solution

1class Solution {
2public:
3    int maximumGain(string s, int x, int y) {
4        int abCount = 0, baCount = 0, score = 0;
5
6        for (char ch : s) {
7            if (ch == 'a') {
8                abCount++;
9            } else if (ch == 'b' && abCount > 0) {
10                score += x;
11                abCount--;
12            }
13
14            if (ch == 'b') {
15                baCount++;
16            } else if (ch == 'a' && baCount > 0) {
17                score += y;
18                baCount--;
19            }
20        }
21
22        return score;
23    }
24};

C# Solution

1public class Solution {
2    public int MaximumGain(string s, int x, int y) {
3        int abCount = 0, baCount = 0, score = 0;
4
5        foreach (char ch in s) {
6            if (ch == 'a') {
7                abCount++;
8            } else if (ch == 'b' && abCount > 0) {
9                score += x;
10                abCount--;
11            }
12
13            if (ch == 'b') {
14                baCount++;
15            } else if (ch == 'a' && baCount > 0) {
16                score += y;
17                baCount--;
18            }
19        }
20
21        return score;
22    }
23}

Conclusion

In this problem, we have to remove substrings from the given string to maximize the score. We've seen a greedy algorithm to solve this problem, which has a linear time complexity. Moreover, we've implemented and explained the solution in Python, JavaScript, Java, C++, and C#. Using this greedy algorithm, you can find the maximum score possible by removing "ab" and/or "ba" substrings from the given string.