#1039：字符串消除

提取主要需求：即消除连续出现的两个以上的字符，直到新生成的字符串不满足条件。

初步分析

设置一个flag标志前一次循环是否有消除操作，如果有，则开始下一次的循环。可该如何判断是否可以消除字符呢？

此时追加一个for循环，将字符串的起始位置设为标记点，检查其后的字符是否与标记点字符相同；
若相同，则将其位置置为终止位置；若不同，则删除首位置元素（放入最终字符串变量result中，该字符串记录算法终止时不可消除的字符）；

伪代码如下：

flag = true; result = "";
while flag 
    j = 2;
    len = input.length;
    for i = 1 to len
        if 下一个字符与首位置字符相同 then : j = j+1;
        else if j > 1 then : 删除j之前的元素; flag = true;
                             截取j之后的子串，替换input;
        else 将首元素加入result，用作下一轮的while消除;
    input = result;

插入操作则可使用for循环，遍历所有课插入位置，得到最高分。

再度思考

基于初步的分析，不难看出插入字符操作并未要求得到插入的具体位置，那么这是否意味着我们可以先进行消除得到一个未插入状态的最终字串，然后再进行插入得到最终字串呢？

好像是可以的？但实际并不对，思考有这种情况：“BCBB”，先进行消除得到未插入字符状态的最终字串，即“BC”，然后插入再消除，发现无论如何插入，最终字串都至少含有一个字符。显然，如果是先进行插入操作得到“BCCBB”，再进行消除得到的最终字串为空串！

对比之下可知，这一步是不可实现的。

那么，消除函数应该是可以更进一步的吧？在初步分析中，假设while循环执行N次（但实际上是不可能执行N次的），for循环N次，我们只记if中的判断条件为有效的基础运算，即3次（最大），则有3N*N = 3N^2 = O(N^2) 的最坏时间复杂度，这么看来，是有提升空间的。

基于以上分析，这一次的消除函数选用栈来进行：

若上一次有发生消除操作，则进入本次的消除检查。
从字符串其实位置开始，主次入栈，每次如栈前检查栈顶元素 == 准备入栈元素。
若不等，栈空间>2则舍弃栈中所有元素，并压入下一元素；否则弹出栈顶元素，计入result字串中。

算法结束时返回最终串与初始串的长度差。

粗略计算，while循环N次（实际并不是），内部的有效基本运算记为m，则算法时间复杂度为 m*N = O(N) 线性阶。

不完整的伪代码如下（这里其实有一个小问题使得算法没能达到线性阶，在哪里呢？）：

flag = true; i = 0; result = "";
while flag 
    s.push(input[i]);
    while input[i++] = s.top()
        s.push(input[i];
    if s.size() > 1 then : s.clear(); flag = true;
    else result += s.top(); s.pop();
    input = result; result = "";

这里只有分析，具体的AC代码和题目链接我都放在了GitHub上，点蓝字即可转到，或者：github.com/ai977313677…
如果你有更好的想法，欢迎讨论。