Reorganize String

class Solution {
public:
    string rearrangeString(string str) {
        vector<int> counts(26, 0);
        for (char c : str) {
            counts[c - 'a']++;
        }
        int maxFreq = 0, mostFreqChar = 0;
        for (int i = 0; i < counts.size(); i++) {
            if (counts[i] > maxFreq) {
                maxFreq = counts[i];
                mostFreqChar = i;
            }
        }
        if (maxFreq > (str.length() + 1) / 2) return "";
        string res = str;
        int idx = 0;
    
        // Place the most frequent character first
        while (counts[mostFreqChar] > 0) {
            res[idx] = char(mostFreqChar + 'a');
            idx += 2;
            counts[mostFreqChar]--;
        }
    
        // Place the rest of the characters
        for (int i = 0; i < counts.size(); i++) {
            while (counts[i] > 0) {
                if (idx >= str.length()) idx = 1;
                res[idx] = char(i + 'a');
                idx += 2;
                counts[i]--;
            }
        }
    
        return res;
    }
};

This C++ solution addresses the task of reorganizing a string so that no two adjacent characters are the same. If the task cannot be achieved, the function returns an empty string. The strategy involves two main parts: counting the frequency of each character using an array and then strategically placing characters based on their frequency to ensure no two adjacent ones are identical.

• Initialize a count vector with size 26 to zero, for each letter of the alphabet.
• Iterate through the input string to populate the count vector with the frequency of each character.
• Identify the character with the maximum frequency. If this frequency is more than half the length of the string rounded up, it is immediately clear that a valid rearrangement isn't possible, so return an empty string.
• Otherwise, create a result string initialized to the input. Begin placing the most frequent character at the alternate indices starting from zero to maintain no adjacent duplicates.
• Once the most frequent character is placed adequately, proceed to place the remaining characters using a similar approach.
• Adjust the index to start from one if the end of the string is reached, continuing the placement in alternating order.

This approach ensures that characters are spread uniformly, preventing any consecutive characters from being identical and providing a valid reorganization, if possible.

class Solution {
    public String rearrangeCharacters(String input) {
        var frequency = new int[26];
        for (char ch : input.toCharArray()) {
            frequency[ch - 'a']++;
        }
        int highestFreq = 0, mostFreqChar = 0;
        for (int i = 0; i < frequency.length; i++) {
            if (frequency[i] > highestFreq) {
                highestFreq = frequency[i];
                mostFreqChar = i;
            }
        }
        if (highestFreq > (input.length() + 1) / 2) {
            return "";
        }
        var resultArray = new char[input.length()];
        int pos = 0;
    
        // Fill positions with the most frequent character first
        while (frequency[mostFreqChar] > 0) {
            resultArray[pos] = (char) (mostFreqChar + 'a');
            pos += 2;
            frequency[mostFreqChar]--;
        }
    
        // Fill positions with remaining characters
        for (int i = 0; i < frequency.length; i++) {
            while (frequency[i] > 0) {
                if (pos >= input.length()) {
                    pos = 1;
                }
                resultArray[pos] = (char) (i + 'a');
                pos += 2;
                frequency[i]--;
            }
        }
    
        return new String(resultArray);
    }
}

The provided Java code defines a method to rearrange characters of a given string so that no two adjacent characters are the same. It returns an empty string if such an arrangement is not possible. Below, you'll find an outlined explanation of the solution:

1. Calculate Frequency of Characters:

   • Initialize an array of size 26 to store the frequency of each character from 'a' to 'z'.
   • Traverse through each character in the input string, updating the frequency array accordingly.

2. Identify the Most Frequent Character:

   • Check the frequency array to find the most frequent character.
   • If the frequency of the most frequent character exceeds half the length of the string (rounded up), return an empty string, indicating no valid reordering is possible.

3. Prepare for Reordering:

   • Initialize a character array for the result, sized to the length of the input string.
   • Start filling this array by placing the most frequent character at even indices first.

4. Distribute Remaining Characters:

   • After placing the most frequent character, iterate over the other characters.
   • Place the remaining characters in the next available even index. If the end of the array is reached, loop back and start placing characters at odd indices.

5. Return the Result:

   • Convert the character array back to a string and return it.

This approach ensures that the characters with higher frequencies are spread out more in the resultant string, hence reducing the chance of adjacent characters being the same. If it is not feasible to avoid consecutive characters due to high frequency of a particular character, the method returns an empty string.

class Solution:
    def rearrangeString(self, str_input: str) -> str:
        frequency = Counter(str_input)
        max_freq, max_char = 0, ''
        for ch, cnt in frequency.items():
            if cnt > max_freq:
                max_freq = cnt
                max_char = ch
        if max_freq > (len(str_input) + 1) // 2:
            return ""
        result = [''] * len(str_input)
        position = 0
    
        # Place the character with the highest frequency first
        while frequency[max_char] > 0:
            result[position] = max_char
            position += 2
            frequency[max_char] -= 1
    
        # Place the remaining characters
        for ch, cnt in frequency.items():
            while cnt > 0:
                if position >= len(str_input):
                    position = 1
                result[position] = ch
                position += 2
                cnt -= 1
    
        return ''.join(result)

The solution provided in Python addresses the reorganization of a string such that no two identical characters are adjacent. Here is a breakdown of how the algorithm works:

• A frequency count of each character in the input string is computed using the Counter from the collections module.
• It then determines the character with the highest frequency. If the frequency of any character exceeds half the length of the input string (plus one if odd), it’s impossible to rearrange the string without repeating adjacent characters, and an empty string is returned.
• An output array of the same length as the input string is initialized. This array will hold the rearranged string.
• The character with the highest frequency is placed first in the output array. Starting from index zero, it populates every second position in the array until all occurrences of this character are exhausted.
• Subsequent characters are placed in the remaining positions using a similar spacing strategy. If the end of the array is reached but there are still characters left to place, the filling continues from the first odd index (index one), thereby ensuring no two identical characters are adjacent.
• Finally, the array is converted back to a string and returned.

This approach efficiently ensures that characters are spread out in a manner that prevents any two identical characters from being adjacent, using straightforward index manipulation and character counting.