Rearrange Letters So No Two Neighbors Match
Implement rearrangeLetters
Rearrange the letters of a string so that no two equal letters are next to each other. Because many arrangements can be valid, this problem asks for one specific arrangement — the one built greedily: at every position, take the letter with the most unused copies among the letters different from the one just placed, and break ties toward the alphabetically smaller letter. If at some position nothing different is available, no valid arrangement exists and the answer is the empty string.
A max-heap of (copies, letter) with a one-step cool-down for the letter just placed carries out that rule in O(log 26) per position, instead of scanning all 26 letters each time.
Example 1:
Input: s = "ddccb"
Output: "cdbcd"
Example 2:
Input: s = "nnnoo"
Output: "nonon"
Example 3:
Input: s = "hhhhij"
Output: ""
+ 10 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ s.length ≤ 30, s contains only lowercase English letters - ●
Build the result one character at a time. At every position, append the letter that has the MOST copies still unused among the letters different from the one just appended; if several letters tie, append the alphabetically smaller one. - ●
If at some position no letter different from the previous one has copies left, no valid arrangement exists — return the empty string "" - ●
Otherwise return the arrangement built by that rule (it always has no two equal neighbors)
s =