Priority Queue Solution ✅✅
IntuitionThe problem requires constructing a string where no character appears more than k consecutive times while maximizing the lexicographical order. To achi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires constructing a string where no character appears more than k consecutive times while maximizing the lexicographical order. To achieve this, the largest characters should be used as much as possible, but when a character reaches its limit of k consecutive occurrences, we temporarily "pause" its usage and switch to the next largest character.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Frequency Counting: Count the frequency of each character using a frequency array.\n2. Max-Heap: Use a priority queue (max-heap) to always process the largest available character.\n3. Building the Result:\n    - Append the current largest character up to k times or until it runs out.\n    - If the current character has more occurrences left, we "pause" it by temporarily skipping to the next largest character.\n    - Insert the skipped character back into the heap to process it later.\n4. Edge Case: If there is no second largest character to "break" the sequence, the construction ends.\n\n# Complexity\n- Time complexity: $$O(Nlog26)$$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(26)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int k) {\n        vector<int> freq(26, 0);\n        for (char c : s) freq[c - \'a\']++;\n        \n        priority_queue<pair<char, int>> pq;\n        for (int i = 0; i < 26; i++) {\n            if (freq[i] > 0) pq.push({\'a\' + i, freq[i]});\n        }\n        \n        string result;\n        while (!pq.empty()) {\n            auto [ch, count] = pq.top(); pq.pop();\n            int used = min(k, count);\n            result.append(used, ch);\n            count -= used;\n\n            if (count > 0) {\n                if (pq.empty()) break;\n                auto [nextCh, nextCount] = pq.top(); pq.pop();\n                result += nextCh;\n                nextCount--;\n\n                if (nextCount > 0) pq.push({nextCh, nextCount});\n                pq.push({ch, count});\n            }\n        }\n        return result;\n    }\n};\n\n```\n``` Java []\nimport java.util.PriorityQueue;\n\nclass Solution {\n    public String repeatLimitedString(String s, int k) {\n        int[] freq = new int[26];\n        for (char c : s.toCharArray()) {\n            freq[c - \'a\']++;\n        }\n        \n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);\n        for (int i = 0; i < 26; i++) {\n            if (freq[i] > 0) pq.offer(new int[] {i + \'a\', freq[i]});\n        }\n        \n        StringBuilder result = new StringBuilder();\n        while (!pq.isEmpty()) {\n            int[] current = pq.poll();\n            int ch = current[0], count = current[1];\n            int used = Math.min(k, count);\n            \n            for (int i = 0; i < used; i++) {\n                result.append((char) ch);\n            }\n            count -= used;\n            \n            if (count > 0) {\n                if (pq.isEmpty()) break;\n                int[] next = pq.poll();\n                result.append((char) next[0]);\n                next[1]--;\n                \n                if (next[1] > 0) pq.offer(next);\n                pq.offer(new int[] {ch, count});\n            }\n        }\n        \n        return result.toString();\n    }\n}\n```\n``` Python []\nimport heapq\nfrom collections import Counter\n\nclass Solution:\n    def repeatLimitedString(self, s: str, k: int) -> str:\n        freq = Counter(s)\n        pq = [(-ord(char), count) for char, count in freq.items()]\n        heapq.heapify(pq)\n        \n        result = []\n        while pq:\n            ch, count = heapq.heappop(pq)\n            ch = chr(-ch)\n            used = min(k, count)\n            result.append(ch * used)\n            count -= used\n            \n            if count > 0:\n                if not pq: break\n                next_ch, next_count = heapq.heappop(pq)\n                result.append(chr(-next_ch))\n                next_count -= 1\n                \n                if next_count > 0:\n                    heapq.heappush(pq, (next_ch, next_count))\n                heapq.heappush(pq, (-ord(ch), count))\n        \n        return "".join(result)\n```
['Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Python3']