561. Keep Twins Apart
A party host has name cards written with single lower-case letters, given as the string s. The cards must be placed in one row so that no two neighbouring cards show the same letter, because identical neighbours would look like twins standing together.
Rearrange all the letters of s into a new string of the same length in which no two adjacent characters are equal, and return it. If no such arrangement exists, return the empty string "".
Several arrangements can be valid; any valid arrangement is accepted. A valid answer uses exactly the same multiset of letters as s and has no equal adjacent characters, or is empty when impossible. Aim for O(n log 26) time.
Example 1
- Input:
- s = "aabbc"
- Output:
- "ababc"
- Explanation:
One valid arrangement is "ababc"; any string with the same letters and no equal neighbours is accepted.
Example 2
- Input:
- s = "zzzy"
- Output:
- ""
- Explanation:
Three z cards cannot be separated by only one other card, so the answer is the empty string.
Example 3
- Input:
- s = "k"
- Output:
- "k"
- Explanation:
A single card trivially has no equal neighbours.
Constraints
- 1 ≤
s.length≤ 105 sconsists of lower-case English letters
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log A), A = 26
- Space
- O(n)