reorganize String

XXX.Reorganize String

String

Greedy

Problem Statement:

Given a string S, rearrange the characters so that no two adjacent characters are the same. If this is not possible, return an empty string.

Algorithm:

1. Count the frequency of each character in the string using a frequency array.
2. Find the character with the highest frequency.
3. Check if the maximum frequency exceeds half the string length (rounded up). If so, return an empty string.
4. Place the most frequent character in even indices of the result array.
5. Fill the remaining characters in the remaining slots of the result array.

Complexity:

Time: O(n), where n is the length of the string | Space: O(1), for the frequency array.

Java Implementation:

public String reorganizeString(String S) {
    int[] hash = new int[26];
    int max = 0, letter = 0;

    // Count the frequency of each character and find the max frequency
    for (int i = 0; i < S.length(); i++) {
        char c = S.charAt(i);
        hash[c - 'a']++;
        if (hash[c - 'a'] > max) {
            max = hash[c - 'a'];
            letter = c - 'a';
        }
    }

    // Check if it's possible to reorganize
    if (max > (S.length() + 1) / 2) return "";

    char[] res = new char[S.length()];
    int idx = 0;

    // Place the most frequent character in even indices
    while (hash[letter] > 0) {
        res[idx] = (char) (letter + 'a');
        idx += 2;
        hash[letter]--;
    }

    // Place the remaining characters
    for (int i = 0; i < hash.length; i++) {
        while (hash[i] > 0) {
            if (idx >= res.length) idx = 1; // Switch to odd indices if needed
            res[idx] = (char) (i + 'a');
            idx += 2;
            hash[i]--;
        }
    }

    return String.valueOf(res);
}
                

Python Implementation:

def reorganizeString(S):
    from collections import Counter
    counts = Counter(S)
    max_count = max(counts.values())
    
    # Check if reorganization is possible
    if max_count > (len(S) + 1) // 2:
        return ""
    
    # Sort characters by frequency
    chars = sorted(counts.keys(), key=lambda x: -counts[x])
    res = [""] * len(S)
    idx = 0
    
    # Fill the most frequent characters in even indices
    for char in chars:
        for _ in range(counts[char]):
            if idx >= len(S):
                idx = 1
            res[idx] = char
            idx += 2
    
    return "".join(res)
                

C++ Implementation:

string reorganizeString(string S) {
    vector count(26, 0);
    for (char c : S) count[c - 'a']++;
    int max_count = *max_element(count.begin(), count.end());
    
    // Check if reorganization is possible
    if (max_count > (S.size() + 1) / 2) return "";

    vector> chars;
    for (int i = 0; i < 26; i++)
        if (count[i] > 0) chars.push_back({count[i], 'a' + i});
    
    sort(chars.rbegin(), chars.rend());
    string res(S.size(), ' ');
    int idx = 0;

    // Fill the most frequent characters in even indices
    for (auto [freq, ch] : chars) {
        for (int i = 0; i < freq; i++) {
            if (idx >= S.size()) idx = 1;
            res[idx] = ch;
            idx += 2;
        }
    }
    return res;
}