Replay Stack of the Most Played Song

A party jukebox keeps a pile of song requests. Design a class PlayStack:

• PlayStack() starts empty.
• push(song) adds one request for song (a string) to the pile.
• pop() removes one request and returns its song: the song with the most requests currently in the pile; if several songs are tied, the one among them whose most recent request was pushed latest. If the pile is empty return "".

Examples

ops:  ["PlayStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop", "pop", "pop", "pop"]
args: [[], ["a"], ["b"], ["a"], ["c"], ["b"], ["a"], [], [], [], [], [], [], []]
Output: [None, None, None, None, None, None, None, "a", "b", "a", "c", "b", "a", ""]
Explanation: "a" has 3 requests and goes first. Then "a" and "b" both have 2 and "b"'s second request
is the newer one. With one request each, the latest-pushed requests win: c, then b, then a.

Constraints

• Up to 2 * 10**4 calls in total; song names are short strings
• Target: push and pop in O(1); searching all songs on every pop is too slow

Goals

• Keep one stack per play count so the answer to pop is always on top of the highest stack
• Maintain the current maximum count in O(1) per operation