A jeweler is restringing a broken necklace. The recovered beads come loose in a bag, and each bead is stamped with a lowercase letter from 'a' to 'z' indicating its color; beads of the same color are indistinguishable from one another.
The jeweler rebuilds the necklace one wave at a time. In a single wave: first, scanning colors from 'a' to 'z', for every color that still has at least one bead remaining in the bag, thread one bead of that color onto the necklace and remove it from the bag; then, scanning colors from 'z' back down to 'a', for every color that still has at least one bead remaining in the bag (after the first scan of this same wave), thread one more bead of that color onto the necklace and remove it. The jeweler repeats waves, one after another, until the bag is completely empty.
Given the bag's contents, reconstruct the exact sequence of bead colors that ends up threaded onto the necklace.
A single line containing a string s of lowercase English letters — the colors of the beads in the bag (their order in the input is irrelevant; only the count of each color matters).
A single line containing the necklace's bead colors, in the exact order they were threaded, as one string of the same length as s.
s consists only of lowercase English letters ('a'-'z').Example 1
Input
aabbccdd
Expected
abcddcba
Explanation
The bag holds two beads each of colors a, b, c, d. In the single wave needed: the increasing scan threads a, b, c, d (one of each, leaving one bead of every color); the decreasing scan then threads d, c, b, a (using up the last bead of each color). The bag is now empty, giving the necklace "abcddcba".
Example 2
Input
leetcode
Expected
cdelotee
Explanation
Counting the bag gives c1, d1, e3, l1, o1, t1. Wave 1's increasing scan threads c, d, e, l, o, t (one of each, leaving e with 2 remaining); its decreasing scan then finds only e still available and threads one more e (leaving 1 e). Wave 1 contributes "cdelot"+"e" = "cdelote". Wave 2's increasing scan finds only e left and threads the final e; its decreasing scan then finds the bag empty. Wave 2 contributes "e". Concatenating gives "cdelote"+"e" = "cdelotee".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →