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

This problem is solved using a greedy approach with the following key steps:

1. Character Frequency Counting:
   • Use a hash array to count the frequency of each lowercase letter.
   • This is done efficiently by mapping 'a' to index 0, 'b' to 1, and so on.
2. Finding the Most Frequent Character:
   • Iterate through the hash array to find the character with the highest frequency.
   • This character is crucial as it's the most likely to cause adjacent duplicates.
3. Placing the Most Frequent Character:
   • Start by placing the most frequent character at even indices (0, 2, 4, ...).
   • This ensures maximum spacing between instances of this character.
4. Feasibility Check:
   • If we can't place all instances of the most frequent character, reorganization is impossible.
   • In this case, we return an empty string.
5. Placing Remaining Characters:
   • Reset the count of the most frequent character to zero in our hash array.
   • Iterate through all characters and place their remaining instances.
   • Use even indices first, then odd indices, alternating to avoid adjacency.
   • If we reach the end of the string, wrap around to the first odd index.

Key Insights:

• The most frequent character is critical. If it can be evenly distributed, other characters can fit in between.
• Using even indices for the most frequent character maximizes the spaces available for other characters.
• The solution is impossible if and only if the count of the most frequent character is greater than (n+1)/2, where n is the string length.

for(int i = 0; i < s.size(); i++) {
    hash[s[i] - 'a']++;
}

This loop is used to count the frequency of each character in the input string s. Let's examine it step by step:

1. for(int i = 0; i < s.size(); i++): This is a standard for loop that iterates through each character in the string s.
   • i starts at 0 and goes up to s.size() - 1.
2. hash[s[i] - 'a']++: This is the key part.
3.  
4. Let's break it down further:

 a. s[i]: This accesses the character at position i in the string s.

 b. s[i] - 'a': This is a clever way to convert a lowercase letter to an index (0-25).

• In ASCII (and Unicode), lowercase letters are consecutive.
• 'a' has an ASCII value of 97, 'b' is 98, 'c' is 99, and so on.
• By subtracting 'a', we get:
  • 'a' - 'a' = 0
  • 'b' - 'a' = 1
  • 'c' - 'a' = 2
  • ...
  • 'z' - 'a' = 25

c. hash[...]: This accesses the element of the hash array at the calculated index.

d. hash[...] ++: This increments the value at that index, effectively counting the occurrence of the character.

Example: Let's say s = "aabbc". Here's how the loop would work:

1. i = 0: s[0] is 'a'
   • 'a' - 'a' = 0, so hash[0] is incremented
   • hash becomes [1, 0, 0, ..., 0]
2. i = 1: s[1] is 'a'
   • 'a' - 'a' = 0, so hash[0] is incremented again
   • hash becomes [2, 0, 0, ..., 0]
3. i = 2: s[2] is 'b'
   • 'b' - 'a' = 1, so hash[1] is incremented
   • hash becomes [2, 1, 0, ..., 0]
4. i = 3: s[3] is 'b'
   • 'b' - 'a' = 1, so hash[1] is incremented again
   • hash becomes [2, 2, 0, ..., 0]
5. i = 4: s[4] is 'c'
   • 'c' - 'a' = 2, so hash[2] is incremented
   • hash becomes [2, 2, 1, 0, ..., 0]

After this loop, hash[0] will contain the count of 'a's, hash[1] the count of 'b's, hash[2] the count of 'c's, and so on.

char max_freq_char;
int max_freq = INT_MIN;
for(int i = 0; i < 26; i++) {
    if(hash[i] > max_freq) {
        max_freq = hash[i];
        max_freq_char = i + 'a';
    }
}

This block finds the character with the highest frequency.

• We initialize max_freq to INT_MIN (the smallest possible integer) to ensure any frequency will be greater.
• We iterate through all 26 positions in the hash array.
• If we find a frequency higher than our current max_freq, we update:
  • max_freq to this new highest frequency
  • max_freq_char to the corresponding character (by adding 'a' to the index)

2. Placing the most frequent character:

int index = 0;
while(max_freq > 0 && index < s.size()) {
    s[index] = max_freq_char;
    max_freq--;
    index += 2;
}

• We start at index = 0 and increment by 2 each time (index += 2).
• We continue while we still have instances of the most frequent character to place (max_freq > 0) and we haven't exceeded the string length (index < s.size()).
• Each iteration, we place the character, decrement max_freq, and move to the next even index.

3. Checking if reorganization is possible: 

if(max_freq != 0) {
    return "";
}

If we still have instances of the most frequent character left to place (max_freq != 0), it means we couldn't fit them all without making them adjacent. In this case, reorganization is impossible, so we return an empty string.

4. Placing the remaining characters:

hash[max_freq_char - 'a'] = 0;
for(int i = 0; i < 26; i++) {
    while(hash[i] > 0) {
        index = index >= s.size() ? 1 : index;
        s[index] = i + 'a';
        hash[i]--;
        index += 2;
    }
}

• First, we reset the count of the most frequent character to 0, as we've already placed all of its instances.
• We iterate through all characters (0 to 25, representing 'a' to 'z').
• For each character with remaining instances (hash[i] > 0):
  • If index has reached or exceeded the string length, we wrap around to 1 (the first odd index).
  • We place the character at the current index.
  • We decrement the count for this character.
  • We move to the next position (incrementing by 2 to alternate between even and odd indices).

This approach ensures that we fill all the gaps left after placing the most frequent character, alternating between even and odd indices to avoid placing identical characters next to each other.

Time Complexity: O(n), where n is the length of the string.

Space Complexity: O(1), as we use a fixed-size array for hashing.

class Solution {
public:
    string reorganizeString(string s) {
        // Hash array to store character frequencies (a-z)
        int hash[26] = {0};
        
        // Count the frequency of each character
        // This is efficient for lowercase English letters
        for(int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a']++;
        }

        // Find the most frequent character
        char max_freq_char;
        int max_freq = INT_MIN;
        for(int i = 0; i < 26; i++) {
            if(hash[i] > max_freq) {
                max_freq = hash[i];
                max_freq_char = i + 'a';
            }
        }

        // Place the most frequent character at even indices
        int index = 0;
        while(max_freq > 0 && index < s.size()) {
            s[index] = max_freq_char;
            max_freq--;
            index += 2;
        }

        // If we couldn't place all instances of the most frequent character,
        // reorganization is impossible
        if(max_freq != 0) {
            return "";
        }

        // Reset the count of the most frequent character
        hash[max_freq_char - 'a'] = 0;

        // Place the remaining characters
        for(int i = 0; i < 26; i++) {
            while(hash[i] > 0) {
                // If we've reached the end of the string, wrap to index 1
                index = index >= s.size() ? 1 : index;
                s[index] = i + 'a';
                hash[i]--;
                index += 2;
            }
        }

        return s;
    }
};