All problems

Remove All Adjacent Duplicates in String

Easy · stack

You are given a string s of lower-case letters.

As long as two equal letters sit next to each other, you may delete both of them. After a deletion the letters on either side of the gap become neighbours and may form a new pair.

Keep deleting until no two equal letters are next to each other, and return the string that is left. It is the empty string if everything is deleted. The final string is the same whichever pair you delete first.

Examples

Example 1

Input: s = "abbaca"

Output: "ca"

Deleting bb leaves aaca, then deleting aa leaves ca.

Example 2

Input: s = "azxxzy"

Output: "ay"

Deleting xx makes the two z letters neighbours, so they go too, leaving ay.

Example 3

Input: s = "aa"

Output: ""

Everything is deleted.

Constraints