Reorganize String

Share

Rearrange characters so no two adjacent chars are same. Return any valid arrangement or "".

Example 1
Input: s="aab" → Output: "aba"
Example 2
Input: s="aaab" → Output: "" (impossible)

Solution Approach

Use a max-heap. Always pick the most frequent character that is different from the previous one.

  • Count character frequencies
  • Use max-heap (by frequency)
  • Each step: poll most frequent (not same as last placed)
  • If only one type left and it equals last, impossible
  • Append character and offer back with decremented count
Java
public String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    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' + a[0]));
        sb.append((char)('a' + b[0]));
        if (--a[1] > 0) pq.offer(a);
        if (--b[1] > 0) pq.offer(b);
    }
    if (!pq.isEmpty()) {
        int[] last = pq.poll();
        if (last[1] > 1) return "";
        sb.append((char)('a' + last[0]));
    }
    return sb.toString();
}
  • Time Complexity: O(n log k)
  • Space Complexity: O(k)