Intuition, Approach and Solution using a Priority Queue in C++(Easy to Understand,Straightforward A)
IntuitionAs it said lexicographically largest my main idea was to solve it using a max heap i.e. a priority queue.(As it will order the characters lexicographic
# Intuition\nAs it said **lexicographically** largest my main idea was to solve it using a max heap i.e. a priority queue.(As it will order the characters lexicographical descending order and make it easy for me to get the correct order for the largest character)\n\n---\n\n\n# Approach\n1. Character Frequency Count\nUse a unordered map to count the frequency of each character in the string.\n2. **Use a Max-Heap (Priority Queue)**\nThe priority queue is used to process characters in lexicographically descending order.\n- Example if a test string is cczazcc\n- Then in the max-heap it would be zzccccaa (descending order)\nPush each character and its frequency into the priority queue.\n3. Build the Result String (Final Ans)\nRepeatedly:\nTake the largest character (top of the heap) and append it to the result up to repeatLimit times.\nIf the character still has remaining frequency(count):\nUse the next largest character (next top of the heap) as a **"Divider/Border"** to satisfy the repeat limit constraint(i.e. the repeatLimit).\nPush both characters (if they have remaining frequency) back into the queue(For updating the queue).\n4. Stop When No Characters Are Left\nIf the queue becomes empty and there\u2019s no character to act as a breaker, stop the process\n\n---\n\n\n# Complexity\n- Time complexity:\nTime Complexity:\nPriority Queue Operations: Each insertion and removal from the priority queue takes **\uD835\uDC42(logn)**, where n is the number of unique characters.\nString Construction: In the worst case, each character is processed multiple times (inserted back into the queue), leading to a total time complexity of **O(klogn)** where k is the length of the string.\n\n- Space complexity:\nThe space complexity is **O(n)** where n is the no of distinct characters in the string its same for both priority queue and the unordered map as both at most store the **n unique no. of characters**\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int repeatLimit) {\n        int len = s.length();\n        string result="";\n\n        //a map is used to count the frequency of each character\n        unordered_map<char, int> mpp;\n        for (char c : s) {\n            mpp[c]++;\n        }\n         \n        // a max-heap so that the largest character is processed first\n        priority_queue<pair<char, int>> pq;\n        for (auto it : mpp) {\n            pq.push({it.first, it.second});\n        }\n        \n        while (!pq.empty()) {\n            auto [ch, count] = pq.top();\n            pq.pop();\n            \n            int k = min(repeatLimit, count);\n            result.append(k, ch);\n            count -= k;\n\n            if (count > 0) {\n               \n                if (pq.empty()) break;\n\n                auto [nextCh, nextCount] = pq.top();\n                pq.pop();\n\n                result.push_back(nextCh);\n                nextCount--;\n\n                pq.push({ch, count});\n                if (nextCount > 0) pq.push({nextCh, nextCount});\n            }\n        }\n\n        return result;\n    }\n};\n```
['Hash Table', 'String', 'Heap (Priority Queue)', 'C++']