Efficient Max-heap solution || Easy to understand
IntuitionThe problem asks us to construct the lexicographically largest string from the characters in s such that no character repeats more than repeatLimit tim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe problem asks us to construct the lexicographically largest string from the characters in s such that no character repeats more than `repeatLimit` times consecutively. This involves:\n\n 1. Using a greedy approach to select the lexicographically largest characters.\n 2. Carefully handling the repeat limit to avoid violating the constraints while maximizing the lexicographical order.\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Frequency Map and Priority Queue:**\n- First, we create a frequency map (`mp`) to count the occurrences of each character in `s`.\n- Use a max-heap (priority queue) to keep track of characters by their lexicographical order (largest characters first).\n\n**2. Building the Result:**\n- Start with an empty result string `res`.\n- While the priority queue is not empty, extract the character with the highest lexicographical order (`it`).\n- If the last character in the result string is not the same as the current character:\n     - Append as many of the current character as possible, up to repeatLimit. If there are remaining occurrences, push the character back into the heap with its updated count.\n- If the last character in the result string is the same as the current character:\n    - Check if the second-largest character is available in the priority queue.\n    - Use that character once to break the sequence of repeated characters.\n    - If no other character is available, stop (as no valid sequence can be constructed).\n\n**3. Priority Queue Updates:**\n- Whenever a character\'s count is reduced and remains non-zero, push it back into the heap with its updated count.\n\n\n\n\n\n\n# Complexity\n- **Time complexity:**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. **Building the Frequency Map:** $$O(n)$$ , where `n` is the length of the string `s`.\n2. **Heap Operations:** Each character can be inserted or extracted from the heap at most once, and heap operations take $$O(log k)$$, where *k* is the number of unique characters in `s`. This results in \n$$O(klogk)$$.\n3. **Appending Characters:** Constructing the result string involves iterating through all characters of `s`, taking $$O(n)$$.\n\nOverall, the time complexity is $$O(n+klogk)$$, where k<=26 .\n\n\n\n\n\n- **Space complexity:**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1. **Frequency Map and Priority Queue:** Both require $$O(k)$$ space, where k<=26.\n2. **Result String:** Requires $$O(n)$$ space to store the final result.\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int repeatLimit) {\n        map<char,int>mp;\n        priority_queue<pair<char,int>>pq;\n        string res="";\n        for(int i=0;i<s.size();i++){\n            mp[s[i]]++;\n        }\n        for(auto it:mp){\n            pq.push({it.first,it.second});\n        }\n        while(!pq.empty()){\n            auto it=pq.top();\n            pq.pop();\n            char c=it.first;\n            int cnt=it.second;\n\n            if(res.empty() or res.back()!=c){\n                if(cnt<=repeatLimit){\n                    while(cnt--){\n                        res+=c;\n                    }\n                }else{\n                    int temp=repeatLimit;\n                    cnt-=repeatLimit;\n                    while(temp--){\n                        res+=c;\n                    }\n                    pq.push({c,cnt});\n                }\n            }else{\n                if(pq.empty())break;\n                char c2=pq.top().first;\n                int cnt2=pq.top().second;\n                pq.pop();\n                res+=c2;\n                cnt2--;\n                if(cnt2>0)pq.push({c2,cnt2});\n                pq.push({c,cnt});\n            }\n        }\n        return res;\n    }\n};\n```
['Hash Table', 'String', 'Greedy', 'Heap (Priority Queue)', 'C++']