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 online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Stack

Erase Pairs 🍇

Learn this problem

● Medium

AmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

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.

Function

erasePairs(S: String) → String

Examples

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".

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".

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!