##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1717.html

# 1717. 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^5
• 1 <= x, y <= 10^4
• s consists of lowercase English letters.

## Solution

Use a greedy approach. If x >= y, then consider removing "ab" first and removing "ba" next. Otherwise, consider removing "ba" first and removing "ab" next.

When removing substrings, update the score and generate the new string after removing the substrings, so that the next steps can be proceeded as well.

Finally, return the score.

• class Solution {
int points = 0;

public int maximumGain(String s, int x, int y) {
if (x >= y) {
s = remove1(s, x);
s = remove2(s, y);
} else {
s = remove2(s, y);
s = remove1(s, x);
}
return points;
}

public String remove1(String s, int x) {
StringBuffer sb = new StringBuffer();
int length = s.length();
int index = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (index > 0 && c == 'b' && sb.charAt(index - 1) == 'a') {
points += x;
sb.deleteCharAt(index - 1);
index--;
} else {
sb.append(c);
index++;
}
}
return sb.toString();
}

public String remove2(String s, int y) {
StringBuffer sb = new StringBuffer();
int length = s.length();
int index = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (index > 0 && c == 'a' && sb.charAt(index - 1) == 'b') {
points += y;
sb.deleteCharAt(index - 1);
index--;
} else {
sb.append(c);
index++;
}
}
return sb.toString();
}
}

############

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;
}
}

• class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
if x < y:
return self.maximumGain(s[::-1], y, x)
ans = 0
stk1, stk2 = [], []
for c in s:
if c != 'b':
stk1.append(c)
else:
if stk1 and stk1[-1] == 'a':
stk1.pop()
ans += x
else:
stk1.append(c)
while stk1:
c = stk1.pop()
if c != 'b':
stk2.append(c)
else:
if stk2 and stk2[-1] == 'a':
stk2.pop()
ans += y
else:
stk2.append(c)
return ans

############

# 1717. Maximum Score From Removing Substrings
# https://leetcode.com/problems/maximum-score-from-removing-substrings/

class Solution:
def maximumGain(self, s: str, x: int, y: int):

def remove(s, target, val):
total = 0
stack = []

for c in s:
stack.append(c)

while len(stack) >= 2 and (stack[-2]+stack[-1]) == target:
stack.pop()
stack.pop()
total += val

return stack, total

if x > y:
s, val1 = remove(s, "ab", x)
s, val2 = remove(s, "ba", y)

return val1 + val2
else:
s, val1 = remove(s, "ba", y)
s, val2 = remove(s, "ab", x)

return val1 + val2

def maximumGain(self, s: str, x: int, y: int):
a = b = res = 0

if x == y:
for i,c in enumerate(s):
if c == "a":
if b > 0:
res += y
b -= 1
else:
a += 1

elif c == "b":
if a > 0:
res += x
a -= 1
else:
b += 1

else:
a = b = 0
else:
checkAB = x > y
used = set()
bdeq = deque()

for i,c in enumerate(s):
if c == "a":
if checkAB:
a += 1
else:
if b > 0:
res += y
b -= 1
else:
a += 1

elif c == "b":
if checkAB:
if a > 0:
res += x
a -= 1
else:
b += 1
bdeq.append(i)
else:
b += 1
bdeq.append(i)

else:
a = b = 0
bdeq.clear()

a = b = 0

for i,c in enumerate(s):
if c != "a" and c != "b":
a = b = 0
else:
if i in used: continue

if c == "a":
if b > 0:
res += y
b -= 1
else:
a += 1

else:
if a > 0:
res += x
a -= 1
else:
b += 1

return res


• class Solution {
public:
int maximumGain(string s, int x, int y) {
if (x < y) {
reverse(s.begin(), s.end());
return maximumGain(s, y, x);
}
int ans = 0;
stack<char> stk1;
stack<char> stk2;
for (char c : s) {
if (c != 'b')
stk1.push(c);
else {
if (!stk1.empty() && stk1.top() == 'a') {
stk1.pop();
ans += x;
} else
stk1.push(c);
}
}
while (!stk1.empty()) {
char c = stk1.top();
stk1.pop();
if (c != 'b')
stk2.push(c);
else {
if (!stk2.empty() && stk2.top() == 'a') {
stk2.pop();
ans += y;
} else
stk2.push(c);
}
}
return ans;
}
};

• func maximumGain(s string, x int, y int) int {
if x < y {
t := []rune(s)
for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
t[i], t[j] = t[j], t[i]
}
return maximumGain(string(t), y, x)
}
ans := 0
var stk1 []byte
var stk2 []byte
for i := range s {
if s[i] != 'b' {
stk1 = append(stk1, s[i])
} else {
if len(stk1) > 0 && stk1[len(stk1)-1] == 'a' {
stk1 = stk1[0 : len(stk1)-1]
ans += x
} else {
stk1 = append(stk1, s[i])
}
}
}
for _, c := range stk1 {
if c != 'a' {
stk2 = append(stk2, c)
} else {
if len(stk2) > 0 && stk2[len(stk2)-1] == 'b' {
stk2 = stk2[0 : len(stk2)-1]
ans += y
} else {
stk2 = append(stk2, c)
}
}
}
return ans
}