A secure research campus prints each visitor badge with a single jumbled tag that mixes the visitor's initials (lowercase letters) with a rotating numeric access code (digits) in no particular order. For the badge scanner to read a tag correctly, its characters must strictly alternate between a letter and a digit — no two letters and no two digits may ever sit next to each other. Given a jumbled tag, rearrange all of its characters (every character must be used exactly once, and no character may be added or removed) into such an alternating string. If several alternating arrangements are possible, any one of them is acceptable. If no alternating arrangement is possible, report that instead by producing an empty output.
A single line containing the tag S.
A single line: any rearrangement of the characters of S in which letters and digits strictly alternate, if one exists; otherwise an empty line.
Example 1
Input
covid2019
Expected
c2o0v1i9d
Explanation
The tag has 5 letters (c, o, v, i, d) and 4 digits (2, 0, 1, 9); their counts differ by only 1, so an alternating arrangement exists. Starting with the more frequent group (letters, since there are more letters than digits) and interleaving one digit after each letter gives c2o0v1i9d — letters and digits strictly alternate throughout.
Example 2
Input
leetcode
Expected
(empty)Explanation
The tag has 8 letters and 0 digits — a difference of 8, which is greater than 1 — so no alternating arrangement can exist (with zero digits available, some two letters would always end up adjacent). The output is therefore an empty line.
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 →