Question 2 #Link

Question 1 :

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:
solution(S) : that, 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.

Example 1:

Input: S =  "CBCAAXA"
Output: "BAX"

Explanation:  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:

Input: S =  "ZYXZYZY"
Output: "XYZ"

Example 3:

Input: S =  "ABCBACDDAA"
Output: ""

Example 4:

Input: S =  "AKFKFNOGKFE"
Output: "AFKMOGB"

Write an efficient algorithm for the following assumptions:
• N is an integer within the range [1...100,000).
• string S is made only of uppercase letters (A-Z).