思路
我们考虑哪些字符不会变成边缘字符。很显然最后的字符串S’中肯定没有相邻字符相同的情况。其实本没有那么难,考虑每个点只会被删除一次,所以除非搜很多遍,复杂度就是 $O(n)$。
我们用双向链表,因为题目也说了,可以知道有且仅有当删除了某些边缘字符后会在当前位置产生新的边缘字符。那么我们先构建双链表,然后考虑从前往后扫描,如果发现当前字符是一个边缘字符就删除这个字符和另外一个需要被删除的字符,然后暂时先不往后走,继续判断当前位置是否产生了新的边缘字符。如果是,则继续删除,知道不再产生新的边缘字符,然后再往后走。
复杂度最优就是 $O(n)$,不会相差太多。