华为OD 消消乐游戏

1. 题意

游戏规则：输入一个只包含英文字母的字符串，字符串中的两个字母如果相邻且相同，就可以消除。
在字符串上反复执行消除的动作，直到无法继续消除为止，此时游戏结束。
输出最终得到的字符串长度。

输入
输入原始字符串 str，需满足：
只能包含大小写英文字母（大小写敏感）；
长度不超过 100。
输出
输出游戏结束后，最终剩余字符串的长度。
备注
若输入中包含非大小写英文字母（如数字、符号等），视为异常输入，直接返回 0。

样例一
input:
gg
output:
0
样例二
input:
adbbdc
output:
2

2. 题解

这个题目应该是比较典型的栈的应用，但是我写的时候没有想到，只想到了双指针的写法，还有bug，没有处理从头开始消去的情况。

2.1 为什么只需要从左往右考虑？

因为消去操作满足交换和结律，因此顺序并不重要，最后得到的字符串一定是一样的。

$$"aaaa"\leftrightarrow "(aa)aa"\leftrightarrow "aa(aa)"\leftrightarrow "a(aa)a"\leftrightarrow "aa"\Rightarrow ""$$

2.2 栈的解法

从左往右逐个处理字符串中的元素，如果当前元素和栈顶元素一样，说明需要执行消去操作，否则就将当前元素入栈。重复操作直到字符串处理完毕，栈中剩余的字符串就是消去后的字符串。

void solve2()
{
    stack<char> st;

    for (auto c: s) {
        if (!st.empty() && st.top() == c ) {
            st.pop();
        }
        else {
            st.push(c);
        }
    }
    
    ans = st.size();
}

2.3 双指针解法

我们可以通过双指针分别往左右扩展来得到需要消去的区间。

初始化时，$r=l+1$，最终我们消去的区间的为$[l+1,r-1]$，因此需要减去的长度为$r-l-1$。

但有一种情况，我们无法处理，那就是之前提到的从后面可以扩展到前面已经消除的区间，比如样例$"aabbcc"$。

所以我们需要去重，为此我们在每次获得了消除完区间后，用一个变量pre_right保存消除区间的右边界。

下一次消除的区间左边界最多扩展到pre_right，就停止扩展以避免重复。

void solve1()
{
    int l = 0;
    int r = l + 1;
    int n = s.size();
    
    ans = n;

    int pre_right = -1;
    while ( r < n) {
        r = l + 1;
        while ( l > pre_right && r < n && (s[l] == s[r])) {
            l--;
            r++;
        }
        //cout << l << " " << r << endl; 
        ans -= ( r - l - 1);

        if ( r - l > 1) {
            pre_right = r - 1;
        }
        
        l = r;
    }

    
}

3. 参考

KJ.JK