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.<ul>
<li>For example, when removing <code>"ab"</code> from <code>"c<u>ab</u>xbae"</code> it becomes <code>"cxbae"</code>.</li>
</ul>
</li>
<li>Remove substring <code>"ba"</code> and gain <code>y</code> points.
<ul>
<li>For example, when removing <code>"ba"</code> from <code>"cabx<u>ba</u>e"</code> it becomes <code>"cabxe"</code>.</li>
</ul>
</li>
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 <= 1051 <= x, y <= 104s consists of lowercase English letters.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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
}
|
