2024寒假每日一题全部题解传送门>>

题目的关键之处就是能快速删除字符串中的边缘字符，在各大数据结构中关于快速删除某个位置，很容易就想到链表，而这题涉及到左右的字符的删除，故采用双链表来做。用双链表做到$O(1)$的删除，再用两个$vector$数组在$O(n)$的时间内模拟出整个删除的过程，这样就能做到$O(n)$的时间复杂度了~

C++代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
int l[N], r[N]; // 表示双向链表中一个节点的左节点和右节点
bool st[N];
char s[N];
vector<int> a; // 存当前所有的边缘字符

void remove(int x) // 删除双链表中的一个节点
{
    l[r[x]] = l[x];
    r[l[x]] = r[x];
}

void check(int x)
{
    if(s[l[x]] == '*' || s[r[x]] == '*') return;

    if(s[x] == s[r[x]] && s[x] != s[l[x]]) 
    {
        a.push_back(l[x]);
        a.push_back(x);
    }

    if(s[x] != s[r[x]] && s[x] == s[l[x]]) 
    {
        a.push_back(x);
        a.push_back(r[x]);
    }
}

int main()
{
    scanf("%s", s + 1);

    int n = strlen(s + 1);

    s[0] = '*', s[n + 1] = '*'; // 在头节点和尾节点加上哨兵，方便判断
    for(int i = 1; i <= n; i ++) 
    {
        l[i] = i - 1;
        r[i] = i + 1;
        check(i);
    }

    while(a.size())
    {
        vector<int> b; // 存删除当前所有的边缘字符后剩下可能是边缘字符的字符
        for(auto t : a)
            if(!st[t]) 
            {
                remove(t);
                st[t] = true;

                b.push_back(l[t]);
                b.push_back(r[t]);
            }

        // 记得一定要把原数组清空，否则会死循环，被卡了半小时...
        a.clear(); 

        for(auto t : b)
            if(!st[t]) 
                check(t);
    }

    bool flag = false;
    for(int i = 1; i <= n; i ++)
        if(!st[i])
        {
            flag = true;
            printf("%c", s[i]);
        }

    if(!flag) puts("EMPTY");

    return 0;
}