A. Plug-in

Codeforces

IDCF81A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Polycarp thinks about the meaning of life very often. He does this constantly, even when typing in the editor. Every time he starts brooding he can no longer fully concentrate and repeatedly presses the keys that need to be pressed only once. For example, instead of the phrase "how are you" he can type "hhoow aaaare yyoouu". Polycarp decided to automate the process of correcting such errors. He decided to write a plug-in to the text editor that will remove pairs of identical consecutive letters (if there are any in the text). Of course, this is not exactly what Polycarp needs, but he's got to start from something! Help Polycarp and write the main plug-in module. Your program should remove from a string all pairs of identical letters, which are consecutive. If after the removal there appear new pairs, the program should remove them as well. Technically, its work should be equivalent to the following: while the string contains a pair of consecutive identical letters, the pair should be deleted. Note that deleting of the consecutive identical letters can be done in any order, as any order leads to the same result. ## Input The input data consists of a single line to be processed. The length of the line is from 1 to 2·105 characters inclusive. The string contains only lowercase Latin letters. ## Output Print the given string after it is processed. It is guaranteed that the result will contain at least one character. [samples]

Polycarp 经常思考生命的意义。他无时无刻不在思考，甚至在打字时也是如此。每次他开始沉思，就无法完全集中注意力，反复按下本应只按一次的键。例如，他本应输入 "how are you"，却可能输入 "hhoow aaaare yyoouu"。 Polycarp 决定自动化纠正此类错误的过程。他打算为文本编辑器编写一个插件，该插件将删除所有相邻的相同字母对（如果文本中存在的话）。当然，这并非 Polycarp 所需的完全解决方案，但他必须从某处开始！帮助 Polycarp 编写核心插件模块。你的程序应从字符串中删除所有相邻的相同字母对。如果删除后出现了新的相邻相同字母对，程序也应继续删除它们。其工作方式在技术上等价于以下过程：只要字符串中存在相邻的相同字母对，就删除该对。注意，删除相邻相同字母对的顺序可以任意，因为任何顺序都会得到相同的结果。输入数据为一行待处理的字符串。该行长度范围为 #cf_span[1] 到 #cf_span[2·105] 个字符（含）。字符串仅包含小写拉丁字母。请输出处理后的字符串。保证结果至少包含一个字符。 ## Input 输入数据为一行待处理的字符串。该行长度范围为 #cf_span[1] 到 #cf_span[2·105] 个字符（含）。字符串仅包含小写拉丁字母。 ## Output 请输出处理后的字符串。保证结果至少包含一个字符。 [samples]

**Definitions** Let $ s \in \{a, b, \dots, z\}^* $ be the input string of length $ n $, where $ 1 \leq n \leq 2 \cdot 10^5 $. **Operation** Define the reduction function $ R: \{a, b, \dots, z\}^* \to \{a, b, \dots, z\}^* $ as follows: While there exists an index $ i $ such that $ s[i] = s[i+1] $, remove the two consecutive identical characters at positions $ i $ and $ i+1 $. This process repeats until no such pair exists. **Constraints** - $ s $ contains only lowercase Latin letters. - $ 1 \leq |s| \leq 2 \cdot 10^5 $. - The final result is guaranteed to be non-empty. **Objective** Compute $ R(s) $, the unique irreducible string obtained by repeatedly removing all consecutive duplicate pairs until none remain.

Samples

Input #1

hhoowaaaareyyoouu

Output #1

wre

Input #2

reallazy

Output #2

rezy

Input #3

abacabaabacabaa

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Plug-in",
    "description": {
      "content": "Polycarp thinks about the meaning of life very often. He does this constantly, even when typing in the editor. Every time he starts brooding he can no longer fully concentrate and repeatedly presses t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF81A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp thinks about the meaning of life very often. He does this constantly, even when typing in the editor. Every time he starts brooding he can no longer fully concentrate and repeatedly presses t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 经常思考生命的意义。他无时无刻不在思考，甚至在打字时也是如此。每次他开始沉思，就无法完全集中注意力，反复按下本应只按一次的键。例如，他本应输入 \"how are you\"，却可能输入 \"hhoow aaaare yyoouu\"。\n\nPolycarp 决定自动化纠正此类错误的过程。他打算为文本编辑器编写一个插件，该插件将删除所有相邻的相同字母对（如果文本中存在的话）。当然，这并非 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{a, b, \\dots, z\\}^* $ be the input string of length $ n $, where $ 1 \\leq n \\leq 2 \\cdot 10^5 $.\n\n**Operation**  \nDefine the reduction function $ R: \\{a, b, \\dots, z\\}^*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments