01
Problem Statement
Given a string s, reorganize it so that no two adjacent characters are the same. Return any valid reorganization, or the empty string "" if it is impossible.
02
Key Observations
- Necessary: If the maximum character frequency is greater than
(n+1)/2, it is impossible (that char would have to be adjacent to itself somewhere). Otherwise a solution exists. - Greedy (max-heap by freq): Use a max-heap of (count, char). Each step: poll the two most frequent (or one if only one left), append them to the result, decrement counts and push back if count > 0. This avoids placing the same char adjacent.
03
Approach
High-level: Count freq; if any count > (n+1)/2 return "". Max-heap (freq, char). While size>=2: poll two, append both, decrement and offer back. If one left append it. Return result.
Steps: int[] freq = new int[26]; for (c : s) freq[c-'a']++; if (max(freq) > (s.length()+1)/2) return ""; PriorityQueue<int[]> pq (freq, char); while (pq.size()>=2) { poll two, append, decrement, offer back; } if (!pq.isEmpty()) append; return sb.toString();
04
Implementation
Java
public String reorganizeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c-'a']++;
}
int max = 0;
for (int f : freq) {
max = Math.max(max, f);
}
if (max > (s.length()+1)/2) {
return "";
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[1]-a[1]);
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
pq.offer(new int[]{i, freq[i]});
}
}
StringBuilder sb = new StringBuilder();
while (pq.size() >= 2) {
int[] a = pq.poll(), b = pq.poll();
sb.append((char)(a[0]+'a')).append((char)(b[0]+'a'));
if (--a[1] > 0) {
pq.offer(a);
}
if (--b[1] > 0) {
pq.offer(b);
}
}
if (!pq.isEmpty()) {
sb.append((char)(pq.poll()[0]+'a'));
}
return sb.toString();
}05
Test Cases
Example 1
Input
s = "aab"
Expected
"aba"Explanation
Valid reorganization.
06
Complexity Analysis
- Time: typically O(n log k) or O(n log n).
- Space: O(k) or O(n).
07
Follow-ups
- Stream: process one element at a time.