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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

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

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

示例 1：

**输入：** s = "cdbcbbaaabab", x = 4, y = 5
**输出：** 19
**解释：**
- 删除 "cdbcbbaaa **ba** b" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaa **ab** " 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcb **ba** a" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbc **ba** " 中加粗的 "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 只包含小写英文字母。

解法一

思路和算法

为了得到最大得分，应使用贪心策略，做法如下。

  • 当 x \ne y 时，应首先执行得分高的删除操作直到无法继续删除，然后执行得分低的删除操作直到无法继续删除。

  • 当 x = y 时，可以按任意顺序执行两种操作。

为方便处理，将 x = y 和 x > y 归入同一种情况，因此有 x \ge y 和 x < y 的两种情况，贪心策略分别如下。

  • 当 x \ge y 时，首先删除字符串中的所有 ab"，然后删除字符串中的所有 ba”。

  • 当 x < y 时，首先删除字符串中的所有 ba"，然后删除字符串中的所有 ab”。

贪心策略的正确性说明如下。

每次操作无论是删除 ab" 还是删除 ba”，都会减少一个 a' 和一个 b’，且剩余字符的相对顺序不变。如果被删除的 ab" 前后都有字母且前后的字母都是 `a' 或 `b'，则删除 ab” 之后，其前后的字母变成相邻，可能有以下情况。

  • 如果前后的字母是 aa" 或 bb”，则在删除 ab" 之前的 4 个相邻字符是 aaba” 或 babb"，无论是删除 ab” 还是删除 ba" 都会剩余两个相同字母，无法一次删除两个相同字母，因此在删除 ab” 的前后，总删除次数不变。

  • 如果前后的字母是 ab"，则在删除 ab” 之前的 4 个相邻字符是 aabb"，在删除 ab” 之后可以一次删除前后的字母 ab"，使用 2 次操作删除 4 个字符，因此在删除 ab” 的前后，总删除次数不变。

  • 如果前后的字母是 ba"，则在删除 ab” 之前的 4 个相邻字符是 baba"，在删除 ab” 之后可以一次删除前后的字母 ba"，使用 2 次操作删除 4 个字符，另一种使用 2 次操作删除 4 个字符的方法是每次删除一个 ba”，因此在删除 ``ab” 的前后，总删除次数不变。

因此每次删除任意位置的 ab" 或 ba” 之后，总删除次数都不变。为了得到最大得分，应将得分高的删除操作次数最大化。

计算最大得分时，可以使用栈模拟删除操作，做法如下。

  • 删除 ``ab” 的过程中，对于每个遍历到的字符，执行如下操作。

    • 如果当前字符是 b' 且栈顶字符是 a’，则需要删除当前的 ``ab”，将栈顶字符 `a’ 出栈，将得分加 x。

    • 否则，将当前字符入栈。

  • 删除 ``ba” 的过程中，对于每个遍历到的字符，执行如下操作。

    • 如果当前字符是 a' 且栈顶字符是 b’，则需要删除当前的 ``ba”，将栈顶字符 `b’ 出栈，将得分加 y。

    • 否则，将当前字符入栈。

执行两轮删除操作之后，即可得到最大得分。

实现方面，可以使用 StringBuffer 或 StringBuilder 类型的可变字符串对象代替栈，可变字符串的左端为栈底，右端为栈顶，拼接和删除字符都在栈顶操作。

代码

[sol1-Java]
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
38
39
40
41
42
43
44
45
46
47
48
49
50
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();
    }
}
[sol1-C#]
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
38
39
40
41
42
43
44
45
46
public 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) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        foreach (char c in s) {
            if (index > 0 && c == 'b' && sb[index - 1] == 'a') {
                points += x;
                sb.Length--;
                index--;
            } else {
                sb.Append(c);
                index++;
            }
        }
        return sb.ToString();
    }

    public string Remove2(string s, int y) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        foreach (char c in s) {
            if (index > 0 && c == 'a' && sb[index - 1] == 'b') {
                points += y;
                sb.Length--;
                index--;
            } else {
                sb.Append(c);
                index++;
            }
        }
        return sb.ToString();
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串 s 两次模拟删除操作，每次遍历的时间是 O(n)。

  • 空间复杂度：O(n)，其中 n 是字符串 s 的长度。每次遍历都需要创建一个长度为 O(n) 的 StringBuffer 或 StringBuilder 类型的对象。

解法二

思路和算法

考虑字符串 s 中的每个只包含 a' 和 b’ 的最长子串，最长字串的含义如下：如果字符串 s 中的所有字符都是 a' 或 b’，则 s 为只包含 a' 和 b’ 的最长子串；如果字符串 s 中有不是 a' 或 b’ 的字符，则以不是 a' 或 b’ 的字符作为分界将 s 分成多个子串，每个用 s 的边界或者字符边界划分的子串都是只包含 a' 和 b’ 的最长子串。

对于每个最长子串，从左到右遍历，遍历过程中计算该最长子串的最大得分。如果 x \ge y 则先考虑删除 ab" 后考虑删除 ba”，如果 x < y 则先考虑删除 ba" 后考虑删除 ab”。

当 x \ge y 时，先考虑删除 ``ab”。从左到右遍历的过程中维护 a' 的个数 count}_1 和 b’ 的个数 count}_2，对于遍历到的每个字符，执行如下操作。

  • 如果当前字符是 `a’，则将 count}_1 加 1。

  • 如果当前字符是 b' 且 count}_1 > 0，则前面一定存在字符 a’ 可以和当前字符 `b’ 组成一个 ab"，删除这个 ab”，将 count}_1 减 1 并将得分加 x。

  • 如果当前字符是 `b’ 且 count}_1 = 0，则不能删除 ``ab”，将 count}_2 加 1。

遍历过程中，每个 b' 都会和前面的 a’ 配对并删除。遍历结束之后，剩余的字母一定满足 b' 在前，a’ 在后，此时不能继续删除 ab"，因此删除 ba”，删除 ``ba” 的次数为 \min(\textit{count}_1, \textit{count}_2)，将得分加 y \times \min(\textit{count}_1, \textit{count}_2)。此时即可得到当前最长子串的最大得分。

当 x < y 时，先考虑删除 ba"，后考虑删除 ab”，使用相同的方法计算当前最长子串的最大得分。

上述做法为使用常数空间的贪心策略。由于优先考虑得分高的删除操作，且删除次数最大化，因此上述贪心策略可以得到最大得分。

实现方面，从左到右遍历字符串 s，对于遍历到的每个字符，如果当前字符为字符串的末尾字符或者当前字符的后一个字符不是 a' 或 b’，则当前字符为一个最长字串的末尾字符，计算当前最长字串的最大得分。

代码

[sol2-Java]
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
class Solution {
    public int maximumGain(String s, int x, int y) {
        int points = 0;
        char c1 = 'a', c2 = 'b';
        if (x < y) {
            c1 = 'b';
            c2 = 'a';
            int temp = x;
            x = y;
            y = temp;
        }
        int count1 = 0, count2 = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char curr = s.charAt(i);
            if (curr == c1) {
                count1++;
            } else if (curr == c2) {
                if (count1 > 0) {
                    count1--;
                    points += x;
                } else {
                    count2++;
                }
            }
            char next = i < length - 1 ? s.charAt(i + 1) : ' ';
            if (next != c1 && next != c2) {
                points += y * Math.min(count1, count2);
                count1 = 0;
                count2 = 0;
            }
        }
        return points;
    }
}
[sol2-C#]
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
public class Solution {
    public int MaximumGain(string s, int x, int y) {
        int points = 0;
        char c1 = 'a', c2 = 'b';
        if (x < y) {
            c1 = 'b';
            c2 = 'a';
            int temp = x;
            x = y;
            y = temp;
        }
        int count1 = 0, count2 = 0;
        int length = s.Length;
        for (int i = 0; i < length; i++) {
            char curr = s[i];
            if (curr == c1) {
                count1++;
            } else if (curr == c2) {
                if (count1 > 0) {
                    count1--;
                    points += x;
                } else {
                    count2++;
                }
            }
            char next = i < length - 1 ? s[i + 1] : ' ';
            if (next != c1 && next != c2) {
                points += y * Math.Min(count1, count2);
                count1 = 0;
                count2 = 0;
            }
        }
        return points;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串 s 一次计算最大得分。

  • 空间复杂度：O(1)。

 Comments
On this page
1717-删除子字符串的最大得分
  1. 解法一
    1. 思路和算法
    2. 代码
    3. 复杂度分析
  2. 解法二
    1. 思路和算法
    2. 代码
    3. 复杂度分析