Reorganize String
The briefingthe full drill, in my own words
The drill: Reshuffle a string's letters so no two identical letters end up next to each other — return one valid arrangement if any exists, or empty if the letters are too lopsided to ever separate.
A string of lowercase letters arrives, and the goal is rearranging its own letters — not choosing new ones — so that no two identical letters end up adjacent.
Some inputs are simply too lopsided to ever separate, when one letter alone makes up more than half the string; in that case the expected answer is an empty result signaling impossibility.
Any valid rearrangement is accepted when one exists — there's no single correct output, just a check that no two neighbors in the returned string match.
- string lengths run up to a few thousand characters
- only lowercase letters appear in the input
- impossible inputs expect an empty string back
- any valid no-adjacent-repeat arrangement is accepted
The hintstake only what you need
HINT 1 THE NUDGE
A letter that shows up more than half the string (rounding up) can never be fully separated from itself — check that ceiling first before trying to build anything.
HINT 2 THE STRUCTURE
Placing the single most frequent remaining letter at every step, as long as it's not the letter you just placed, keeps every other letter's options open the longest.
HINT 3 ONE STEP FROM THE ANSWER
Keep letter counts in a max-heap. Pop the most frequent, place it, and if it's the same letter you just placed, temporarily pop the second-most-frequent instead — then push whatever still has count left back in.
Coach's boardthe pattern, step by step
Counts start a=3, b=2, c=1 over 6 letters. The heaviest letter, 3, isn't over half of 6, so a valid arrangement exists.
The splitstwo paces, two languages
class Solution:
def reorganizeString(self, s: str) -> str:
counts = collections.Counter(s)
n = len(s)
if counts and max(counts.values()) > (n + 1) // 2:
return ""
heap = [(-c, ch) for ch, c in counts.items()]
heapq.heapify(heap)
result = []
while heap:
c1, ch1 = heapq.heappop(heap)
if result and result[-1] == ch1:
if not heap:
return ""
c2, ch2 = heapq.heappop(heap)
result.append(ch2)
c2 += 1
if c2 < 0:
heapq.heappush(heap, (c2, ch2))
heapq.heappush(heap, (c1, ch1))
else:
result.append(ch1)
c1 += 1
if c1 < 0:
heapq.heappush(heap, (c1, ch1))
return "".join(result)class Solution:
def reorganizeString(self, s: str) -> str:
counts = collections.Counter(s)
letters = sorted(counts) # fixed scan order
n = len(s)
def backtrack(remaining, last):
if remaining == 0:
return ""
for ch in letters:
if counts[ch] > 0 and ch != last:
counts[ch] -= 1
rest = backtrack(remaining - 1, ch)
if rest is not None:
return ch + rest
counts[ch] += 1 # backtrack, this placement led nowhere
return None
result = backtrack(n, "")
return result if result is not None else ""class Solution {
public String reorganizeString(String s) {
int[] counts = new int[26];
for (char c : s.toCharArray()) {
counts[c - 'a']++;
}
int n = s.length();
int maxCount = 0;
for (int c : counts) {
maxCount = Math.max(maxCount, c);
}
if (maxCount > (n + 1) / 2) {
return "";
}
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[1] - a[1]); // [charIndex, count]
for (int i = 0; i < 26; i++) {
if (counts[i] > 0) {
heap.offer(new int[] { i, counts[i] });
}
}
StringBuilder sb = new StringBuilder();
while (!heap.isEmpty()) {
int[] top = heap.poll();
if (sb.length() > 0 && sb.charAt(sb.length() - 1) - 'a' == top[0]) {
if (heap.isEmpty()) {
return "";
}
int[] second = heap.poll();
sb.append((char) ('a' + second[0]));
second[1]--;
if (second[1] > 0) {
heap.offer(second);
}
heap.offer(top);
} else {
sb.append((char) ('a' + top[0]));
top[1]--;
if (top[1] > 0) {
heap.offer(top);
}
}
}
return sb.toString();
}
}class Solution {
public String reorganizeString(String s) {
int[] counts = new int[26];
for (char c : s.toCharArray()) {
counts[c - 'a']++;
}
List<Character> letters = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) {
if (counts[c - 'a'] > 0) {
letters.add(c);
}
}
char[] buffer = new char[s.length()];
return backtrack(0, s.length(), '\0', letters, counts, buffer) ? new String(buffer) : "";
}
private boolean backtrack(int pos, int n, char last, List<Character> letters, int[] counts, char[] buffer) {
if (pos == n) {
return true;
}
for (char ch : letters) {
if (counts[ch - 'a'] > 0 && ch != last) {
counts[ch - 'a']--;
buffer[pos] = ch;
if (backtrack(pos + 1, n, ch, letters, counts, buffer)) {
return true;
}
counts[ch - 'a']++; // backtrack, this placement led nowhere
}
}
return false;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED