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
- Initialize two counters
abCount
andbaCount
to count occurrences of substrings "ab" and "ba". - Initialize a variable
score
to store the total score. - 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' andabCount
> 0, that means we can remove a "ab" substring (pair previous 'a' with this 'b'), so increment the score byx
and decrement theabCount
. c. If the current character is 'b', incrementbaCount
. d. If the current character is 'a' andbaCount
> 0, that means we can remove a "ba" substring (pair previous 'b' with this 'a'), so increment the score byy
and decrement thebaCount
. - 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.