Reorganize String

• This approach is not implemented due to its extreme inefficiency. The general algorithm would be:
• 1. Define a recursive function, say generatePermutations, that explores all possible orderings of the characters in s.
• 2. To handle duplicate characters, use a frequency map of characters rather than swapping elements in an array to generate unique permutations.
• 3. In the recursive function, at each step, try to append every available character (from the frequency map) to the current permutation string.
• 4. Before appending, check if the character is the same as the last character added. If it is, skip this choice.
• 5. Once a permutation of length n is formed, it is a valid solution. Return it.
• 6. If the recursion completes without finding a solution, it's impossible.

The brute-force method involves exploring every single arrangement of the characters in the string s. This can be achieved using a backtracking algorithm. We would try to build a valid string character by character. At each position, we would try to place an available character, ensuring it's not the same as the character at the previous position. If we successfully build a string of the same length as s, we have found a solution. If we explore all possibilities and fail to do so, no solution exists. Due to the massive number of permutations (n!), this approach is computationally infeasible for the given constraints.

• 1. Count Frequencies: Create a frequency map (e.g., a HashMap or an array of size 26) to store the counts of each character in s.
• 2. Check for Impossibility: Find the maximum frequency maxFreq. If maxFreq > (n + 1) / 2, where n is the length of s, return "" as no solution is possible.
• 3. Build Max Heap: Create a PriorityQueue to act as a max heap. Populate it with pairs of (frequency, character) for all characters with a count greater than zero. The heap should be ordered by frequency in descending order.
• 4. Construct the String: Initialize an empty StringBuilder.
• 5. Greedy Selection Loop: While the heap is not empty:
  • Poll the element with the highest frequency, let's call it current.
  • Append current.character to the StringBuilder.
  • If a previous element (the one polled in the last iteration) exists and its decremented frequency is greater than 0, add it back to the heap. This one-step delay prevents the same character from being chosen twice in a row.
  • Decrement the frequency of current.
  • Set previous = current.
• 6. Return Result: Convert the StringBuilder to a string and return it.

This greedy strategy works by prioritizing the most frequent characters. A max heap is the perfect data structure for this, as it always provides the element with the highest priority (in this case, frequency) in O(log A) time, where A is the alphabet size.

The core of the algorithm is to iteratively build the result string. In each step, we extract the most frequent character from the heap and append it to our result. To ensure no two adjacent characters are the same, we don't immediately put this character back into the heap. Instead, we hold onto it and only add it back in the next iteration, after we've appended a different character. This ensures separation. We repeat this process until the heap is empty.

An initial check is crucial: if any character appears more than (n + 1) / 2 times, it's impossible to arrange them without two being adjacent. This is because to separate k instances of a character, you need at least k - 1 other characters to place in between.

1class Solution {2    public String reorganizeString(String s) {3        Map<Character, Integer> counts = new HashMap<>();4        for (char c : s.toCharArray()) {5            counts.put(c, counts.getOrDefault(c, 0) + 1);6        }7 8        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> counts.get(b) - counts.get(a));9        maxHeap.addAll(counts.keySet());10 11        // Check for impossibility12        if (counts.get(maxHeap.peek()) > (s.length() + 1) / 2) {13            return "";14        }15 16        StringBuilder res = new StringBuilder();17        char prev = ' '; // Placeholder for previous character18        int prevCount = 0;19 20        while (!maxHeap.isEmpty()) {21            char current = maxHeap.poll();22            res.append(current);23            24            // Add the previous character back to the heap if it still has counts left25            if (prev != ' ' && prevCount > 0) {26                maxHeap.add(prev);27            }28 29            // Update previous character to be the current one for the next iteration30            prev = current;31            prevCount = counts.get(current) - 1;32            counts.put(current, prevCount);33        }34 35        return res.toString();36    }37}

• 1. Count Frequencies: Create an integer array counts of size 26 to store the frequency of each character ('a' through 'z').
• 2. Find Most Frequent: Iterate through the counts array to find the character with the highest frequency (maxFreq) and its corresponding character (maxChar).
• 3. Check for Impossibility: If maxFreq > (n + 1) / 2, return "".
• 4. Initialize Result Array: Create a character array res of size n.
• 5. Place Most Frequent Character: Place all instances of maxChar into the res array at even indices (0, 2, 4, ...). Keep track of the current index.
• 6. Place Remaining Characters: Iterate through the counts array again (from 'a' to 'z'). For each character:
  • While its count is greater than 0, place it into the res array.
  • If the index for placement goes beyond the array bounds, reset it to 1 (to start filling odd positions).
  • Place the character and advance the index by 2.
  • Decrement the character's count.
• 7. Return Result: Convert the res character array into a string and return it.

This method is based on the same greedy principle but uses a more direct construction. The key insight is that if a solution is possible, the most frequent character is the biggest obstacle. By placing it first with maximum spacing (i.e., at every other position), we create slots between them. Then, we can fill these slots and the remaining positions with the rest of the characters.

For example, if 'a' is the most frequent character in 'aaabcc', we would first place the 'a's: a _ a _ a _. Then we fill the blanks with the other characters: a b a c a c. This strategy guarantees a valid arrangement if one exists, because the initial check (maxFreq <= (n + 1) / 2) ensures we have enough other characters to fill the gaps between the most frequent one.

1class Solution {2    public String reorganizeString(String s) {3        int n = s.length();4        int[] counts = new int[26];5        for (char c : s.toCharArray()) {6            counts[c - 'a']++;7        }8 9        int maxFreq = 0;10        int maxCharIndex = 0;11        for (int i = 0; i < 26; i++) {12            if (counts[i] > maxFreq) {13                maxFreq = counts[i];14                maxCharIndex = i;15            }16        }17 18        if (maxFreq > (n + 1) / 2) {19            return "";20        }21 22        char[] res = new char[n];23        int index = 0;24 25        // 1. Place the most frequent character26        while (counts[maxCharIndex] > 0) {27            res[index] = (char) (maxCharIndex + 'a');28            index += 2;29            counts[maxCharIndex]--;30        }31 32        // 2. Place the rest of the characters33        for (int i = 0; i < 26; i++) {34            while (counts[i] > 0) {35                if (index >= n) {36                    index = 1; // Wrap around to fill odd indices37                }38                res[index] = (char) (i + 'a');39                index += 2;40                counts[i]--;41            }42        }43 44        return new String(res);45    }46}