Rearrange a String So No Neighbors Match
The D.E. Shaw Group● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given a string s of lowercase English letters. Rearrange all of its letters so that no two neighboring letters are the same. Every letter must be used exactly as many times as it appears in s.
Many arrangements can be valid, so return the lexicographically smallest one: compare two strings from left to right, and the first position where they differ decides which one is smaller, using alphabetical order.
If no arrangement keeps every pair of neighbors different, return the empty string "".
Function
rearrangeNoAdjacentEqual(s: String) → StringExamples
Example 1
s = "aab"return = "aba"The two copies of a must be split by the b. The only valid arrangement is aba.
Example 2
s = "aaab"return = ""The letter a appears 3 times in a string of length 4. Three copies of a need at least 2 other letters between them, but there is only one b, so no valid arrangement exists.
Example 3
s = "aabbcc"return = "abacbc"The answer starts with aba. After that, the remaining letters are one b and two c. Choosing b next would leave cc, which cannot be placed without two neighboring c letters, so the next letter is c. The rest is bc, giving abacbc.
Example 4
s = "vvvlo"return = "vlvov"The letter v appears 3 times in a string of length 5, so it must take positions 1, 3, and 5. That forces the answer to start with v even though l and o come earlier in the alphabet. The smaller letter l goes in position 2 and o in position 4, giving vlvov.
Constraints
1 <= s.length <= 10^5sconsists only of lowercase English letters.