思路
如果纯模拟的话,要遍历O(n^2)次,而数组删除元素也是O(n),这样铁tle,考虑优化:
(1)删除元素用双链表实现
https://www.acwing.com/activity/content/problem/content/864/
(2)每次删出边缘字符后,新的边缘字符可能出现在删除的边缘字符的两边,故可以用两个集合分别统计边缘字符和待判字符
c++代码O(n)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int r[N],l[N];
vector<int> q,w;//q表示待判字符,w表示遍历一次找到的边缘字符
string s;
bool st[N];
int n;
void insert(int k)
{
if(!st[k])
{
st[k] = true;
w.push_back(k);
}
}
void filter()
{
w.clear();
for(int k : q)
{
int a = l[k],b = r[k];
if(s[a] == s[k] && s[k] != s[b] && s[b] != '#')
insert(k),insert(b);
else if(s[a] != s[k] && s[k] == s[b] && s[a] != '#')
insert(a),insert(k);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> s;
n = s.size();
s = " " + s;
s[0] = s[n + 1] = '#';
for(int i = 1;i <= n;i++)
{
l[i] = i - 1;
r[i] = i + 1;
q.push_back(i);
}
r[0] = 1;
l[n + 1] = n;
while(true)
{
filter();
if(w.empty()) break;
q.clear();
for(int k : w)
{
int a = l[k],b = r[k];
if(!st[a] && a && (q.empty() || a != q.back()))
q.push_back(a);
if(!st[b] && b != n + 1)
q.push_back(b);
r[a] = b,l[b] = a;
}
}
if(r[0] != n + 1)
for(int i = r[0];i != n + 1;i = r[i])
cout << s[i];
else cout << "EMPTY" << endl;
return 0;
}