题目

给你一个字符串 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 <= 10^5
• 1 <= x, y <= 10^4
• s 只包含小写英文字母。

思路

对于这道题，贪心算法是一个非常有效的策略。因为这道题使用贪心并不会对最后的结果有影响，所以我们只需要考虑的分高的字符串，优先删除它们即可。

考虑一个字符串片段，也是删除顺序唯一的会冲突的情况，也就是 前...aba...后 和 前...bab...后 ，我们这里只看前者。

• 如果我们先删除 "ab"（假设 x 分），字符串会变成 前...a...后。
• 如果我们先删除 "ba"（假设 y 分），字符串会变成 前...a...后。

也就是说，删除实际上不造成差别上的影响，因此我们唯一要考虑的就是每次删除的得分。那么我们当然应该每次都选择得分更高的选项。那么总体上我们也可以先整体删除得分高的字符串，再删除得分低的字符串。

那么，在具体实现上，直接在字符串上反复查找和删除效率很低（每次删除都可能导致 O(N) 的移动），一个高效的实现是使用栈（Stack）。我们可以遍历一次字符串，用一个临时字符串（或栈）来存储处理过的、无法删除的字符。

• 第一轮（处理高分对）：遍历输入字符串 s。对于每个字符 c：
  • 如果临时字符串不为空，且其最后一个字符和当前字符 c 能够组成高分对（比如临时字符串末尾是 'a'，当前 c 是 'b'，且 x > y），那么我们就找到了一个 "ab"。
  • 这时，我们弹出临时字符串的最后一个字符（相当于删除了 'a'），也不把当前字符 c（也就是 'b'）加入，然后将得分 x 加到总分上。
  • 否则，不满足删除条件，就将当前字符 c 压入临时字符串。
• 第二轮（处理低分对）：第一轮结束后，我们得到的临时字符串是一个不包含任何高分对的新字符串。现在，我们对这个新字符串重复同样的过程，只不过这次我们寻找的是低分对（比如 "ba"）。
• 将两轮得到的分数相加，即为最大总分。

代码实现

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        stack<char> stack1;
        stack<char> stack2;
        char higher;
        char lower;
        int higher_point;
        int lower_point;
        int result = 0;
        if(x > y)
        {
            higher = 'a'; lower = 'b'; higher_point = x; lower_point = y;
        }
        else
        {
            higher = 'b'; lower = 'a'; higher_point = y; lower_point = x;
        }
        
        for(char i : s)
        // 第一轮
        {
            if(!stack1.empty())
            {
                if(stack1.top() == higher && i == lower)
                {
                    stack1.pop();
                    result += higher_point;
                }
                else
                {
                    stack1.push(i);
                }
            }
            else
            {
                stack1.push(i);
            }
        }

        while(!stack1.empty())
        // 第二轮
        {
            char temp = stack1.top();
            stack1.pop();

            if(!stack2.empty())
            {
                if(temp == lower && stack2.top() == higher) //注意判断
                {
                    stack2.pop();
                    result += lower_point;
                }
                else
                {
                    stack2.push(temp);
                }
            }
            else
            {
                stack2.push(temp);
            }
        }

        return result;

    }
};

优化思路

代码使用了两个 stack，这涉及到两次完整的字符串遍历和数据结构操作。我们可以通过使用“原地”处理（in-place）的思路来显著优化，减少数据结构的开销和内存的反复读写。优化思路是使用指针模拟栈操作。

具体上，使用一个写指针 在一个字符数组或字符串上模拟栈的操作，优化如下：

1. 缓存友好：数据被保存在一块连续的内存中（如 string 或 vector），CPU 访问速度远快于 stack 默认使用的 deque。
2. 减少开销：避免了 push/pop 的函数调用开销和数据结构内部的管理开销。

优化后思路如下：

• 第一次处理（高分组合）：
  • 创建一个字符串 s1 作为缓冲区。
  • 使用一个索引 write_idx 作为 s1 的写指针，初始为 0。
  • 遍历输入字符串 s。对于每个字符 c：
    • 如果 write_idx > 0 并且 s1[write_idx - 1] 和 c 能组成高分组合，那么就 write_idx-- （相当于 pop），并加上分数。
    • 否则，就执行 s1[write_idx] = c，然后 write_idx++（相当于 push）。
  • 处理完毕后，s1 中从 0 到 write_idx-1 的部分就是第一轮剩下的字符串。
• 第二次处理（低分组合）：
  • 现在，我们对第一次处理后得到的有效字符串（s1的前 write_idx 个字符）进行第二次处理。
  • 我们可以复用 s1 的空间。再引入一个新的写指针 final_write_idx，初始为 0。
  • 遍历 s1 从 0 到 write_idx-1 的部分。
  • 采用和第一轮完全相同的逻辑，只不过这次是寻找低分组合。
  • 最终累加的分数就是结果。

优化后代码

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int total_score = 0;
        
        // 使用swap
        char char1 = 'a', char2 = 'b';
        if (x < y) {
            swap(x, y);
            swap(char1, char2);
        }

        // 第一次处理
        int write_idx = 0; // 写指针
        for (char read_char : s) {
        
            // 当前字符先写入
            s[write_idx] = read_char;
            
            // 如果写入后，能和前一个字符组成高分组合
            if (write_idx > 0 && s[write_idx - 1] == char1 && s[write_idx] == char2) {
                // 写指针回退
                write_idx -= 2; 
                total_score += x;
            }
            // 写指针前进
            write_idx++;
        }

        // 使用 s 的 [0, write_idx) 部分，这是第一轮处理后剩下的字符串
        int remaining_len = write_idx;

        // 第二次处理
        write_idx = 0; // 重置写指针，复用 s 的前半部分空间
        for (int i = 0; i < remaining_len; ++i) { // 遍历第一轮剩下的部分
            char read_char = s[i];
            s[write_idx] = read_char;

            if (write_idx > 0 && s[write_idx - 1] == char2 && s[write_idx] == char1) {
                write_idx -= 2;
                total_score += y;
            }
            write_idx++;
        }

        return total_score;
    }
};

复杂度分析