1. 題意

游戲規則：輸入一個只包含英文字母的字符串，字符串中的兩個字母如果相鄰且相同，就可以消除。
在字符串上反復執行消除的動作，直到無法繼續消除為止，此時游戲結束。
輸出最終得到的字符串長度。

輸入
輸入原始字符串 str，需滿足：
只能包含大小寫英文字母（大小寫敏感）；
長度不超過 100。
輸出
輸出游戲結束后，最終剩余字符串的長度。
備注
若輸入中包含非大小寫英文字母（如數字、符號等），視為異常輸入，直接返回 0。

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

2. 題解

這個題目應該是比較典型的棧的應用，但是我寫的時候沒有想到，只想到了雙指針的寫法，還有bug，沒有處理從頭開始消去的情況。

2.1 為什么只需要從左往右考慮？

因為消去操作滿足交換和結律，因此順序并不重要，最后得到的字符串一定是一樣的。

$$"aaaa"?"(aa)aa"?"aa(aa)"?"a(aa)a"?"aa"?""$$

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