天书破解：消除重复子串算法实现

天书破解：消除重复子串算法实现

天书是由26个大写英文字母组成的长字符串。天书的破解依赖于以下消除操作：每次消去长度大于2的极长相同字母子串。'极长'的意思该子串的两端不能是这子串的字母。例如，JKWWWWLB的包含W的极长相同子串是中间WWWW，而WW不是极长子串。消去WWWW子串后，结果子串为JKLB。

通过多次消除操作，能得到长度最短的结果子串就是破解的天书。请你设计一种方案，输出天书破解后的字符数。

输入格式

数据有若干行。每一行只有一个字符串S。当S为0时，表示输入结束。

输出格式

按照输入的顺序，输出天书破解后的字符数，每个数字占一行。

输入示例

JKWWWWLB
AAABBBA
WWKKAAAKWA
0

输出示例

4
0
1

C++ 代码

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    while (cin >> s && s != "0") {
        int len = s.length();
        while (len > 2) {
            bool flag = false;
            for (int i = 1; i < len - 1; i++) {
                if (s[i] == s[i - 1] && s[i] == s[i + 1]) {
                    s.erase(i, 1);
                    len--;
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                break;
            }
        }
        cout << len << endl;
    }
    return 0;
}