425. Cancel Case Pairs

A text editor has an odd autocorrect rule: whenever two neighbouring letters are the same letter but written in different cases (such as g beside G, in either order), both are deleted at once. Deleting a pair can bring two new letters together, so the rule keeps firing until no such neighbours remain.

Given the string s of English letters, return what is left once nothing more can be cancelled. The result may be an empty string. The order in which pairs are cancelled does not change the outcome, so the answer is unique.

Example 1

Input:
s = "kLlKmoOn"
Output:
"mn"
Explanation:

Ll cancels, then K and k meet and cancel too, then oO cancels. Left with mn.

Example 2

Input:
s = "xYyXXz"
Output:
"Xz"
Explanation:

Yy cancels, which makes x touch X so they cancel as well. What remains is Xz.

Constraints

1 ≤ s.length ≤ 100000
s contains only lower-case and upper-case English letters.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.

Expected complexity

Time
O(n)
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…