How should I practice Erase Pairs 🍇?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Erase Pairs 🍇 associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Stack

Erase Pairs 🍇

● MediumAmazonFULLTIMEOA

See Amazon hiring insights

You are given a string S. In one move you can erase from S a pair of identical letters. Find the shortest possible string that can be created this way. If there are many such strings, choose the alphabetically (lexicographically) smallest one. Note that there is no limit to the number of moves.

Write a function:

given a string S of length N, returns the shortest string (or the first alphabetically, in the case of a draw) created by erasing pairs of identical letters from S.

Examples

01 · Example 1

S = "CBCAAXA"
return = "BAX"

For the input string S, you can make, for example, two moves: First, erase a pair of letters "C": "CBCAAXA" ➝ "BAAXA". Then, erase a pair of letters "A": "BAAXA" ➝ "BAX". Thus the string "BAX" is created. There is no way to create a shorter string. The other string of length 3 that can be created is "BXA", but "BAX" is the first alphabetically. The function should return "BAX".

02 · Example 2

S = "ZYXZYZY"
return = "XYZ"

First, erase a pair of letters "Y": "ZYXZYZY" ➝ "ZXZYZ". Then, erase a pair of letters "Z": "ZXZYZ" ➝ "XYZ". The other strings of length 3 that can be created are "ZYX", "YXZ", "XZY" and "ZXY", but "XYZ" is alphabetically the first, so the function should return "XYZ".

03 · Example 3

S = "ABCBACDDAA"
return = " "

For S = "ABCBACDDAA" all five pairs of identical letters can be erased. The function should return "" (empty string).

Constraints

N/A (If you know about it, feel free to contact us ;D tysm!