Reorganize String

How it works

Instead of building the string character by character, we can place characters at alternating indices. First, fill all even indices (0, 2, 4, ...) with the most frequent character. This guarantees no two identical characters are adjacent since they are separated by at least one position. Then fill the remaining positions with other characters, wrapping to odd indices when even slots are exhausted. We use idx to track the current position and update it using idx += 2.

Steps

1. Count frequencies in freq and find the most frequent character at maxIdx.
2. If the max frequency exceeds (n + 1) / 2, return an empty string.
3. Place the most frequent character at indices 0, 2, 4, ... until exhausted.
4. For all remaining characters i:
   • Place them at the current idx, incrementing by 2 each time.
   • When the idx exceeds n, wrap to idx = 1 and continue with odd positions.
5. Return the res string.

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space, since we have at most 26 different characters.
  • O(n) space for the output string.

Things to watch for

Incorrect Impossibility Check

The condition for impossibility is when the most frequent character appears more than (n + 1) / 2 times. Using n / 2 or forgetting the ceiling division leads to incorrect rejection of valid inputs or acceptance of impossible cases.

Placing Characters at Wrong Indices in Greedy Approach

When using the index-based greedy approach, characters must be placed at even indices first (0, 2, 4, ...) before wrapping to odd indices. Failing to reset the index to 1 after exceeding the array length results in index out-of-bounds errors or incorrect placements.

Re-inserting the Same Character into the Heap Immediately

In the heap-based approach, the just-used character must be held back for one iteration before reinsertion. Pushing it back immediately allows it to be selected again on the next pop, creating adjacent duplicates.

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1

        max_idx = freq.index(max(freq))
        max_freq = freq[max_idx]
        if max_freq > (len(s) + 1) // 2:
            return ""

        res = [''] * len(s)
        idx = 0
        max_char = chr(max_idx + ord('a'))

        while freq[max_idx] > 0:
            res[idx] = max_char
            idx += 2
            freq[max_idx] -= 1

        for i in range(26):
            while freq[i] > 0:
                if idx >= len(s):
                    idx = 1
                res[idx] = chr(i + ord('a'))
                idx += 2
                freq[i] -= 1

        return ''.join(res)

class Solution {
public:
    string reorganizeString(string s) {
        vector<int> freq(26, 0);
        for (char& c : s) {
            freq[c - 'a']++;
        }

        int maxIdx = max_element(freq.begin(), freq.end()) - freq.begin();
        int maxFreq = freq[maxIdx];
        if (maxFreq > (s.size() + 1) / 2) {
            return "";
        }

        string res(s.size(), ' ');
        int idx = 0;
        char maxChar = 'a' + maxIdx;

        while (freq[maxIdx] > 0) {
            res[idx] = maxChar;
            idx += 2;
            freq[maxIdx]--;
        }

        for (int i = 0; i < 26; i++) {
            while (freq[i] > 0) {
                if (idx >= s.size()) {
                    idx = 1;
                }
                res[idx] = 'a' + i;
                idx += 2;
                freq[i]--;
            }
        }

        return res;
    }
};