algoadvance

Leetcode 767. Reorganize String

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 an empty string if not possible.

Clarifying Questions

  1. Input Constraints: What is the length range of the string s?
    • Typically, it is 1 <= s.length <= 500.
  2. Character Set: Are the characters in s purely lowercase English letters?
    • Yes, the input constraint generally mentions lowercase English letters only.

Strategy

  1. Frequency Count:
    • First, calculate the frequency of each character in the string s.
  2. Max-Heap for Frequency:
    • Use a max-heap to store characters by their frequency. This helps in always picking the most frequent character available.
  3. Greedily Place Characters:
    • Extract characters from the heap and place them in the result string ensuring no two adjacent characters are the same.
    • Use a temporary variable to hold the previously placed character and ensure it’s not placed in the next position.
  4. Check for Feasibility:
    • During this process, if at any point we cannot place a character without violating the adjacency constraint and yet some characters are left, return an empty string.

Time Complexity

Here’s the implementation in C++:

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

string reorganizeString(string s) {
    // Step 1: Count the frequency of each character.
    unordered_map<char, int> freq;
    for(char c : s) {
        freq[c]++;
    }
    
    // Step 2: Put characters into a max-heap based on their frequency.
    priority_queue<pair<int, char>> maxHeap;
    for(auto& entry : freq) {
        maxHeap.push({entry.second, entry.first});
    }
    
    // Step 3: Build the resulting string.
    string result = "";
    pair<int, char> prev(0, '#');
    
    while(!maxHeap.empty()) {
        auto current = maxHeap.top();
        maxHeap.pop();
        
        // Append current character to the result.
        result += current.second;
        
        // If the previous character has more frequency left, push it back to the heap.
        if(prev.first > 0) {
            maxHeap.push(prev);
        }
        
        // Update previous with the current (but reduce the frequency).
        current.first--;
        prev = current;
    }
    
    // Final check to make sure the rearrangement is valid.
    for(int i = 1; i < result.size(); ++i) {
        if(result[i] == result[i-1]) {
            return "";
        }
    }
    
    return result;
}

// Example usage
int main() {
    string s = "aab";
    cout << reorganizeString(s) << endl;  // Possible output: "aba"
    
    s = "aaab";
    cout << reorganizeString(s) << endl;  // Possible output: ""
    
    return 0;
}

Feel free to ask any questions or request clarifications on the above solution!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI