跳转至

1717. 删除子字符串的最大得分

题目描述

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

  • 删除子字符串 "ab" 并得到 x 分。
    • 比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
  • 删除子字符串"ba" 并得到 y 分。
    • 比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

 

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

 

提示：

  • 1 <= s.length <= 105
  • 1 <= x, y <= 104
  • s 只包含小写英文字母。

解法

方法一

 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
}

评论