Priority Queue (Max Heap) solution in easy way. (java, c++, python)
ApproachSteps to Solve the ProblemUnderstand the Problem:You are given a string s with lowercase letters.
You need to construct a new string where:
Any characte
# Approach\n# Steps to Solve the Problem\n\n**Understand the Problem:**\n\nYou are given a string s with lowercase letters.\nYou need to construct a new string where:\nAny character can appear consecutively at most limit times.\nThe resulting string should be lexicographically the largest possible.\nUse a greedy approach with a priority queue (max-heap) to ensure you always select the largest character available.\n\n# Steps to Solve the Problem:\n\n**Step 1: Count Frequencies**\nUse a HashMap (or similar data structure) to count the occurrences of each character in the string.\n\n**Step 2: Add Characters to a Max-Heap**\nAdd all characters to a priority queue (max-heap) so you can always get the largest available character.\n\n**Step 3: Build the Resulting String**\nUse a StringBuilder (or string in Python/C++) to append characters while respecting the limit constraint.\n\n1. If the count of the current character is less than or equal to limit, append all occurrences.\n2. If the count exceeds limit, append limit occurrences, then:\nTemporarily select the next largest character to break the repetition.\n3. Return the original character back to the heap if it still has remaining occurrences.\n\n**Step 4: Edge Cases**\nEnsure proper handling when the priority queue becomes empty or when characters are exhausted.\n\n# Complexity\n- Time complexity:\n**O( n log k )** where n= length of string and k= no of unique char in string\n\n- Space complexity:\n**O(n)**\n\n# Code\n```java []\nclass Solution {\n    public String repeatLimitedString(String s, int limit) {\n        HashMap<Character,Integer> map= new HashMap<>();\n        for(char c: s.toCharArray()) map.put(c,map.getOrDefault(c,0)+1);\n        PriorityQueue<Character> pq= new PriorityQueue<>((a,b)->b-a);\n        for(char k: map.keySet()) pq.offer(k);\n        StringBuilder sb= new StringBuilder();\n        while(!pq.isEmpty()){\n            char c=pq.poll();\n            int count=map.get(c);\n            if(count<=limit){\n                for(int i=0;i<count;++i) sb.append(c);\n                map.remove(c);\n            }\n            else{\n                for(int i=0;i<limit;++i) sb.append(c);\n                map.put(c,map.get(c)-limit);\n                if(pq.isEmpty()) return sb.toString();\n                char next=pq.poll();\n                sb.append(next);\n                map.put(next,map.get(next)-1);\n                if(map.get(next)==0) map.remove(next);\n                if(map.containsKey(next)) pq.offer(next);\n                pq.offer(c);\n            }\n        }\n        return sb.toString();\n    }\n}\n```\n``` C++ []\n#include <queue>\n#include <unordered_map>\n#include <string>\n\nclass Solution {\npublic:\n    std::string repeatLimitedString(std::string s, int limit) {\n        std::unordered_map<char, int> freq;\n        for (char c : s) freq[c]++;\n        \n        // Max-heap to store characters in decreasing order\n        std::priority_queue<char> pq;\n        for (auto& it : freq) pq.push(it.first);\n        \n        std::string result;\n        \n        while (!pq.empty()) {\n            char curr = pq.top();\n            pq.pop();\n            int count = freq[curr];\n            \n            // If count <= limit, append all occurrences\n            if (count <= limit) {\n                result.append(count, curr);\n                freq.erase(curr);\n            }\n            // If count > limit\n            else {\n                result.append(limit, curr);\n                freq[curr] -= limit;\n\n                if (pq.empty()) break; // Can\'t break repetition if no other character exists\n                \n                // Append the next largest character to break repetition\n                char next = pq.top();\n                pq.pop();\n                result.push_back(next);\n                freq[next]--;\n                \n                // Return characters with remaining occurrences back to the heap\n                if (freq[next] > 0) pq.push(next);\n                pq.push(curr);\n            }\n        }\n        \n        return result;\n    }\n};\n```\n``` Python3 []\nimport heapq\nfrom collections import Counter\n\nclass Solution:\n    def repeatLimitedString(self, s: str, limit: int) -> str:\n        freq = Counter(s)\n        # Max-heap (use negative values to simulate a max-heap)\n        pq = [-ord(char) for char in freq]\n        heapq.heapify(pq)\n        \n        result = []\n        \n        while pq:\n            curr = -heapq.heappop(pq)\n            char = chr(curr)\n            count = freq[char]\n            \n            if count <= limit:\n                result.append(char * count)\n                del freq[char]\n            else:\n                result.append(char * limit)\n                freq[char] -= limit\n                \n                if not pq:\n                    break  # Can\'t break repetition if no other character exists\n                \n                # Append the next largest character to break repetition\n                next_char = chr(-heapq.heappop(pq))\n                result.append(next_char)\n                freq[next_char] -= 1\n                \n                # Return characters with remaining occurrences back to the heap\n                if freq[next_char] > 0:\n                    heapq.heappush(pq, -ord(next_char))\n                heapq.heappush(pq, -ord(char))\n        \n        return "".join(result)\n```
['String', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3']