text of lowercase English letters and an integer gap. Rearrange the letters so that any two equal letters are at least gap apart (positions i and j are |i − j| apart). With gap ≤ 1 there is no restriction.
There are usually many valid rearrangements, so build this particular one. Fill the string from left to right; at each position consider the letters that still have copies left and did not appear in any of the previous gap − 1 positions. Among them, take the letter with the most copies left, breaking ties by taking the one earliest in the alphabet.
If at some position no letter fits, return the empty string "". That happens exactly when no valid rearrangement exists.text="ppqqr", gap=2 → 'pqpqr'
Step 0: p and q have 2 copies each, take p. Step 1: p was just used, take q. Step 2: p and q have one copy each, p comes first. Step 3: q. Step 4: r. The result is pqpqr.
text="xxxy", gap=2 → ''
Three copies of x at least 2 apart need a string of length at least 5, but there are only 4 letters.
text="banana", gap=0 → 'aanabn'
text="ppqqr", gap=2
'pqpqr'
Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.