767. Reorganize String

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

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: ""

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Bit Manipulation (Thao tác bit)Heap / Priority Queue (Heap / Hàng đợi ưu tiên)String (Chuỗi)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0767-reorganize-string.cpp

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<int, int> um;
        
        for (char c : s) {
            um[c]++;
        }
        
        priority_queue<pair<int, char>> pq;
        
        for (const auto &[v, c] : um) {
            pq.push({c, v});
        }
        
        string ans = "";
        
        while (pq.size() > 1) {
            auto [c1, v1] = pq.top();
            pq.pop();
            
            auto [c2, v2] = pq.top();
            pq.pop();
            
            c1--, c2--;
            ans.push_back(v1);
            ans.push_back(v2);
            
            if (c1 > 0) {
                pq.push({c1, v1});
            }
            
            if (c2 > 0) {
                pq.push({c2, v2});
            }
        }
        
        if (!pq.empty()) {
            if (pq.top().first > 1) {
                return "";
            }
            else {
                return ans + pq.top().second;
            }
        }
        
        return ans;
    }
};