UOJ Logo LFYZ Online Judge

LFYZOJ

#323. 字符串(string)

统计

问题描述

现在给一个字符串,你要做的就是当这个字符串中存在两个挨着的字符是相同的时就将这两个字符消除。需要注意的是,当把这两个字符消除后,可能又产生一对新的挨着的字符是相同的。比如,初始的字符串是abcddcdd是两个挨着的相同的字符,当把dd消除后,得到的字符串是abcc,这时cc又是两个挨着的相同的字符,所以又应该把cc消除。重复以上操作直到剩下的串中不存在两个挨着的字符是相同的为止,输出最终剩下的串。另外需要注意的是,多对相同字符的消除顺序是不会对答案产生影响的,可以证明最后他们都会达到唯一的结果,比如,对于初始字符串adccdeed,无论是adccdeed->addeed->aeed->ad还是adccdeed->adccdd->adcc->ad,最终的输出结果都是ad

输入格式

输入的第一行,包含一个字符串,为初始字符串,所有的字符均为小写字母。

输出格式

输出为一行,包含一个字符串,为执行多次消除操作后最终剩下的字符串。

样例一

input

adccdeed

output

ad

数据范围与约定

对于 $100\%$ 的数据,字符串的长度在 $1$ 到 $200000$ 之间。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$