算法：字符串消除問題的數學證明

問題：

給定一個字符串，僅由A、B、C3個字母組成。當出現連續兩個不同的字母時，你可以用另外一個字母替換它，如有AB或BA連續出現，你把它們替換為字母C；有AC或CA連續出現時，你可以把它們替換為字母B；有BC或CB連續出現時，你可以把它們替換為字母A。可以不斷反復按照這個規則進行替換，目標是使得最終結果所得到的字符串盡可能短，求最終結果的最短長度。

輸入：字符串。長度不超過200，僅由ABC3個字母組成。輸出：按照上述規則不斷消除替換，所得到的字符串最短的長度。

例如：

輸入CAB，輸出2。因為我們可以把它變為BB或者變為CC。

輸入BCAB，輸出1。我們可以把它變為AAB到AC到B，也可以把它變為BBB，但因為前者長度更短，所以輸出1。

先給出幾個概念

純字符串：只含有一種字母的字符串稱為純字符串，例如AAA就是一個純字符串

混字符串：含有至少兩種字母的字符串稱為混字符串，例如ABC就是一個混字符串

最優長度：字符串通過消除的最終結果的最短長度，稱為該字符串的最優長度。上面的示例中，CAB的最優長度為2，BCAB的最優長度為1

最優串：字符串通過消除達到最優長度時的字符串稱為最優串，最優串可能不止一個。如CAB的最優串為BB和CC，而BCAB的最優串為B。最優串一定是純字符串

統計向量：用（X，Y，Z）表示字符串的統計向量，其中X、Y、Z分別表示字符串中字母A、B、C的個數。上面的示例中，CAB的統計向量為（1，1，1），BCAB的統計向量為（1，2，1）

統計特征向量：用（X，Y，Z）表示字符串的統計特征向量，其中X、Y、Z分別表示字符串中字母A、B、C的個數的奇偶性，用“奇”、“偶”表示。CAB的統計特征向量為（奇，奇，奇），BCAB的統計特征向量為（奇，偶，奇）

再給出幾個推論

推論1：純字符串的最優長度就是純字符串的長度。

很明顯的，只有一個字母，沒法消除，所以最優長度就是純字符串的長度

推論2：在純字符串前或后加另一個字母得到新的混字符串，則新混字符串的最優長度為1

例如：BBBBBBBA。則消除的過程是，BBBBBBBA >> BBBBBBC >> BBBBBA >> BBBBC >> BBBA >> BBC >> BA >> C

其他的類似，不再贅述

推論3：若純字符串的長度為偶數，則在前或后添加另一個字母得到新的混字符串，則新混字符串的最優串為添加的字母；若純字符串的長度為奇數，則新混字符串的最優串為剩下的一個字母

假設純字符串為BB，添加字母A，則新混字符串為BBA，BBA >> BC >> A

假設純字符串為BBBB，添加字母A，則新混字符串為BBBBA，BBBBA >> BBA >> A

以此類推，推論3的前半部得證

假設純字符串為B，添加字母A，則新混字符串為BA，BA >> C

假設純字符串為BBB，添加字母A，則新混字符串為BBBA，BBBA >> BA >> C

以此類推，推論3的后半部得證

推論4：混字符串的最優長度不超過2（為1或2）

證明：

首先混字符串通過不停的消除，最終能得到一個純字符串（因為若還有不同的字母，則必相鄰，則還能繼續消除）。

若該純字符串的長度為1或2，則證明了該推論（不過，就算純字符串長度為2，還沒證明最優長度一定是2，可以肯定的是最優長度不超過2，即1或2都有可能）

若該純字符串的長度大于2，不失一般性，假設該純字符串的長度為K（K＞2），該純字符串都由字母B組成（字母A、C是一樣的），該純字符串是通過N（N≥1）步消除得到的

那么回退一步，第N-1步消除得到的混字符串為B……BACB……B，其中A前面有K₁個B，C后面有K₂個B，K₁+K₂=K-1。（也有可能是B……BCAB……B，和B……BACB……B是一致的，不再贅述了）

那么，根據K₁和K₂的取值不同，可以優化出不同的消除

K₁是奇數，K₂是奇數。利用推論3，可知B……BA >> C；CB……B >> A；B……BACB……B >> CA >> B，最優串是B，最優長度為1

K₁是奇數，K₂是偶數。利用推論3，可知B……BA >> C；CB……B >> C；B……BACB……B >> CC，則最優長度不超過2（因為還沒法證明最優長度不會是1）

K₁是偶數，K₂是奇數。利用推論3，可知B……BA >> A；CB……B >> A；B……BACB……B >> AA，則最優長度不超過2（因為還沒法證明最優長度不會是1）

K₁是偶數，K₂是偶數。利用推論3，可知B……BA >> A；CB……B >> C；B……BACB……B >> AC >> B，最優串是B，最優長度為1

綜上所述，混字符串的最優長度不超過2

推論5：統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字符串的最優長度為2；其余的混字符串的最優長度為1

證明：

考察一下，每次消除，統計特征向量的變化過程

假設字符串的統計特征向量為（奇，奇，奇）

假設消除是AC（或CA） >> B，則A和C的個數減1，而B的個數增加1，則統計特征向量變為（偶，偶，偶）

假設消除是AB（或BA） >> C，則A和B的個數減1，而C的個數增加1，則統計特征向量變為（偶，偶，偶）

假設消除是BC（或CB） >> A，則B和C的個數減1，而A的個數增加1，則統計特征向量變為（偶，偶，偶）

綜上所述，統計特征向量為（奇，奇，奇）的混字符串，經過1次消除后，統計特征向量變為（偶，偶，偶）

同理可證，統計特征向量為（偶，偶，偶）的混字符串，經過1次消除后，統計特征向量變為（奇，奇，奇）

由此可知，反復消除后，統計特征向量為（奇，奇，奇）的混字符串的最優串的統計特征向量是（偶，偶，偶）。（因為最優串是純字符串，只能有1種字符，所以最優串不可能是（奇，奇，奇））

同理可證，統計特征向量為（偶，偶，偶）的混字符串的最優串的統計特征向量也是（偶，偶，偶）。

因此，統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字符串的最優串的統計特征向量為（偶，偶，偶）

假設字符串的統計特征向量為（奇，偶，偶）

假設消除是AC（或CA） >> B，則A和C的個數減1，而B的個數增加1，則統計特征向量變為（偶，奇，奇）

假設消除是AB（或BA） >> C，則A和B的個數減1，而C的個數增加1，則統計特征向量變為（偶，奇，奇）

假設消除是BC（或CB） >> A，則B和C的個數減1，而A的個數增加1，則統計特征向量變為（偶，奇，奇）

綜上所述，統計特征向量為（奇，偶，偶）的混字符串，經過1次消除后，統計特征向量變為（偶，奇，奇）

同理可證，統計特征向量為（偶，奇，奇）的混字符串，經過1次消除后，統計特征向量變為（奇，偶，偶）

由此可知，反復消除后，統計特征向量為（奇，偶，偶）的混字符串的最優串的統計特征向量是（奇，偶，偶）。（因為最優串是純字符串，只能有1種字符，所以最優串不可能是（偶，奇，奇））

同理可證，統計特征向量為（偶，奇，奇）的混字符串的最優串的統計特征向量也是（奇，偶，偶）。

因此，統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字符串的最優串的統計特征向量為（奇，偶，偶）

同理可證

統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字符串的最優串的統計特征向量為（偶，奇，偶）

統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字符串的最優串的統計特征向量為（偶，偶，奇）

由推論4可知，混字符串的最優長度不超過2

如果，混字符串的最優長度為1，則最優串是A，統計特征向量是（奇，偶，偶）；是B，統計特征向量是（偶，奇，偶）；是C，統計特征向量是（偶，偶，奇）

如果，混字符串的最優長度為2，則最優串是AA或BB或CC，統計特征向量是（偶，偶，偶）

所以，統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字符串的最優長度是2。

統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字符串的最優長度為1，最優串是A

統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字符串的最優長度為1，最優串是B

統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字符串的最優長度為1，最優串是C

證明完畢

結論：

1、純字符串的最優串就是自身，最優長度就是自身的長度

2、統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字符串的最優長度為2

3、其余的混字符串的最優長度是1，其中統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字符串的最優串是A；統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字符串的最優串是B；統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字符串的最優串是C