noodleProblems/
Remove All Adjacent Duplicates In String
#118

Remove All Adjacent Duplicates In String

AlgorithmeasyStringStack

You are given a string s of lowercase letters. A **duplicate removal** deletes two *adjacent* equal characters.

Repeatedly perform duplicate removals on s until no two adjacent characters are equal, then return the final string. The result is guaranteed to be unique.

Example cases

  • one collapse
    in s = "abbaca"
    out "ca"
    Remove "bb" to get "aaca", then "aa" to get "ca".
  • cascade
    in s = "azxxzy"
    out "ay"
    Remove "xx" to get "azzy", then the newly adjacent "zz" to get "ay".
  • no removals
    in s = "abc"
    out "abc"

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
Saved
s =
"abbaca"