Rearrange a string so no neighbours match

Given a string s of lowercase English letters, rearrange its characters so that no two adjacent characters are equal. Every character of s must be used exactly once.

Implement:

1. reorganize(s) -> str: return any valid arrangement, or "" if none exists.
2. reorganize_smallest(s) -> str: return the lexicographically smallest valid arrangement, or "" if none exists. The result is unique, so it can be graded exactly.

Constraints

• 0 <= len(s) <= 10^5
• s contains only a-z.

Example 1

s = "ccbbaa"
reorganize(s)          -> any valid answer, e.g. "cbacba"
reorganize_smallest(s) -> "abacbc"

Example 2

s = "aabbbb"
reorganize(s)          -> ""   (four b's cannot be separated by two a's)

Interviewers often start with part 1 and then ask for the deterministic answer, or ask that equal letters be at least k positions apart.

Reconstructed from the reported question; details may differ from what interviewers ask.