線上程式設計解題之神秘消失

一、題目詳情

在書架上擺着一些書，這些書隻有兩種顔色，要麼是黃色，要麼是藍色，突然某一天這些書被施了魔法，如果一本黃色和一本藍色的書挨着，這兩本書就會消失不見，然後右邊的書會往左邊移動，直到和左邊的書挨着，如果這兩本顔色不同，這兩本書又會神秘消失。現在給你一個隻包含A和B的字元串s(1<=|s|<=100000)，其中A表示黃色的書，B表示藍色的書，問這n本書中最多會消失多少本書。

輸入一個字元串s，s中A表示黃色的書，B表示藍色的書

輸出最多會消失多少本書

示例1

輸入：

"AABB"

輸出：

4

二、解題思路

解題主要找的是問題的關鍵點和對問題的了解程度，這道題的關鍵點有兩個：

關鍵點一：消失。

如果一本黃色和一本藍色的書挨着，這兩本書就會消失不見。解讀一下就是A與B挨着就會同時消失。再了解一下就是，消失的書本數量是2的倍數。

關鍵點二：挨着。

不管有多少本書，也不管怎麼放，必定會有一本黃色和一本藍色的書挨着。比如一種極端的情況就是示例中展示的：“AABB”。而AB挨着的結果就是AB同時消失。再換一個思路，如果AB不想不會同時消失，唯一的可能性就是你隻有A或者隻有B。

根據題目，結合關鍵點，可以得出以下結論：

1. N本書擺在書架上，最後隻會剩下A或者B（依據關鍵點二）
2. 消失書本的數量是A或者B數量的兩倍（依據關鍵點一）

時間複雜度：O(1)

空間複雜度：O(1)