Reorganize String - Leetcode Solution

Problem Statement:

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab" Output: "aba"

Example 2:

Input: s = "aaab" Output: ""

Approach:

The problem requires us to rearrange the input string such that no two adjacent characters are the same. We can approach the problem in the following way:

1. First, we need to count the frequency of each character in the input string s. We can do this by creating a hash table that will store the count of each character.

2. Next, we need to sort the characters in decreasing order of frequency. We can do this by creating a priority queue that will sort the characters based on their count.

3. We can now start constructing the result string by appending the most frequent character to the result string first. Then we can append the next most frequent character to the result string, but only if it is not the same as the last character in the result string. We repeat this process until the result string is fully constructed.

4. If at any point we encounter a character that cannot be added to the result string without violating the condition of not having two adjacent characters that are the same, we return "".

Solution:

class Solution { public: string reorganizeString(string s) {

    // Count the frequency of each character in the string
    unordered_map<char, int> countMap;
    for (char c : s) {
        countMap[c]++;
    }
    
    // Create a priority queue to sort the characters in decreasing order of frequency
    priority_queue<pair<int, char>> pq;
    for (auto it : countMap) {
        pq.push({it.second, it.first});
    }
    
    // Construct the result string
    string result = "";
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (result.empty() || curr.second != result.back()) {
            result += curr.second;
            if (--curr.first > 0) {
                pq.push(curr);
            }
        } else {
            return "";
        }
    }
    
    return result;
}

};

Complexity Analysis:

Time Complexity: O(nlogn), where n is the length of the input string s. We need to count the frequency of each character in the input string s which takes O(n) time. Sorting the characters in decreasing order of frequency using a priority queue takes O(nlogn) time in the worst case. Constructing the final string also takes O(n) time.

Space Complexity: O(n), where n is the length of the input string s. We need to store the count of each character in the input string s in a hash table which takes O(n) space. We also need to use a priority queue to sort the characters, which can take up to O(n) space in the worst case.

1