How should I practice Shortest String After Erasing Equal Pairs?

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

Is Shortest String After Erasing Equal Pairs associated with Marshall Wace?

FastPrep tags this as a Marshall Wace online assessment coding practice problem when the problem catalog has that company and stage context.

Shortest String After Erasing Equal Pairs

Marshall Wace● MediumNEW GRADOA

Problem statement

Choose two equal letters at any positions in S and delete them. The other letters keep their relative order. You may repeat this operation as often as you want.

Return a result of minimum possible length. If several results have that length, return the lexicographically smallest one, using the usual alphabetical order from A to Z.

The answer may be the empty string. Rearranging the remaining letters is not allowed.

Function

solution(S: String) → String

Examples

Example 1

S = "CBCAAXA"return = "BAX"

Delete both C letters, then two A letters. A shortest result has length three; BAX is smaller than the other attainable result BXA.

Example 2

S = "ZYXZYZY"return = "XYZ"

Delete one pair of Y letters and one pair of Z letters, keeping a subsequence XYZ. Other shortest results include ZYX, YXZ, XZY and ZXY.

Example 3

S = "ABCBACDDAA"return = ""

Every letter has an even count, so all letters can be removed in equal pairs.

Example 4

S = "AKFKFMOGKFB"return = "AFKMOGB"

Retain one occurrence of each odd-frequency letter. Among the feasible subsequences of that minimum length, AFKMOGB is first alphabetically.

Constraints

1 <= S.length <= 100000.
S contains only uppercase English letters A through Z.