Given a string s of lowercase letters, rearrange its characters so that no two neighbouring characters are the same. Return any such arrangement, or an empty string "" if it is impossible.
- 1 <= s.length <= 500
- s has only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying permutations is exponential. Instead look at the most frequent character with count maxf. Its copies need a different character between each pair, so it is impossible exactly when maxf > (n + 1) / 2. Otherwise there is a simple construction: write the most frequent character on the even indices first, then continue placing the other characters on the remaining even indices and wrap around to the odd ones. Equal characters always land two apart, so they never touch.
Algorithm
- Count every letter and find the most frequent one.
- If its count is greater than
(n + 1) / 2, return"". - Place the most frequent letter at indices 0, 2, 4, and so on.
- Place every other letter on the next free even index, switching to index 1, 3, 5 once the even indices run out.
- Join and return the result.
O(n)Space: O(n) for the output (26 counters otherwise)class Solution: def reorganizeString(self, s: str) -> str: n = len(s) count = Counter(s) best = max(count, key=count.get) if count[best] > (n + 1) // 2: return "" # impossibleΒ res = [""] * n idx = 0 # Most frequent letter on even indices first for _ in range(count[best]): res[idx] = best idx += 2 del count[best] # Remaining letters: continue on even indices, then wrap to odd ones for ch, c in count.items(): for _ in range(c): if idx >= n: idx = 1 res[idx] = ch idx += 2 return "".join(res)