Reorganize String

Problem Statement

Given a string, reorganize it so no two adjacent characters are the same. If impossible, return "". This medium-level greedy problem is about rearrangement—space out those letters!

Example

Input: s = "aab"

Output: "aba"

Input: s = "aaab"

Output: "" (impossible)

Code

public class Solution {
    public String reorganizeString(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        int maxCount = 0, maxChar = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                maxChar = i;
            }
        }
        if (maxCount > (s.length() + 1) / 2) return "";
        char[] result = new char[s.length()];
        int idx = 0;
        while (count[maxChar] > 0) {
            result[idx] = (char) (maxChar + 'a');
            count[maxChar]--;
            idx += 2;
        }
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                if (idx >= s.length()) idx = 1;
                result[idx] = (char) (i + 'a');
                count[i]--;
                idx += 2;
            }
        }
        return new String(result);
    }
}
            

def reorganize_string(s):
    count = {}
    for c in s: count[c] = count.get(c, 0) + 1
    max_count, max_char = max((v, k) for k, v in count.items())
    if max_count > (len(s) + 1) // 2: return ""
    result = [''] * len(s)
    idx = 0
    while count[max_char] > 0:
        result[idx] = max_char
        count[max_char] -= 1
        idx += 2
    for c in count:
        while count[c] > 0:
            if idx >= len(s): idx = 1
            result[idx] = c
            count[c] -= 1
            idx += 2
    return ''.join(result)
            

function reorganizeString(s) {
    let count = {};
    for (let c of s) count[c] = (count[c] || 0) + 1;
    let maxCount = 0, maxChar = '';
    for (let c in count) {
        if (count[c] > maxCount) {
            maxCount = count[c];
            maxChar = c;
        }
    }
    if (maxCount > Math.floor((s.length + 1) / 2)) return "";
    let result = new Array(s.length);
    let idx = 0;
    while (count[maxChar] > 0) {
        result[idx] = maxChar;
        count[maxChar]--;
        idx += 2;
    }
    for (let c in count) {
        while (count[c] > 0) {
            if (idx >= s.length) idx = 1;
            result[idx] = c;
            count[c]--;
            idx += 2;
        }
    }
    return result.join('');
}
            

Explanation

• Greedy Choice: Place the most frequent character in even positions, then fill others.
• Flow: Check feasibility, interleave characters.
• Example: "aab" → "aba" by placing 'a' at 0,2, 'b' at 1.

Note