Easyyy Pessyyy Solution ✅ | Beats 80% Runtime 🔥 | 100% Memory 🔥
Intuition
The goal is to build the lexicographically largest string while ensuring no character appears more than repeatLimit times consecutively.
Count Charact
\n# Intuition\n* The goal is to build the lexicographically largest string while ensuring no character appears more than repeatLimit times consecutively.\n\n### Count Character Frequency:\nUse a frequency array to count occurrences of each character.\n\n### Max-Heap for Character Priority:\nStore characters in a max-heap (priority queue) based on their lexicographical order and frequency. The heap ensures the largest character is processed first.\n\n### Construct the String:\n\n* Append the largest character up to repeatLimit times.\n* If it still has remaining occurrences, temporarily switch to the next largest character to break the consecutive limit.\n* Push both characters back into the heap if they have remaining occurrences.\n### Repeat until no valid characters remain.\n\n# Approach\n1. Count Frequency:\nUse an array of size 26 to count the frequency of each character.\n\n2. Max-Heap Initialization:\nInsert all characters (with positive frequency) into a max-heap. The heap will sort characters in descending lexicographical order based on their index.\n\n3. String Construction:\n* Use the largest character as much as allowed (repeatLimit) before switching to the next largest character.\n* Reinsert characters into the heap if they still have a remaining count after appending.\n\n# Complexity\n### Time complexity:\n##### Frequency Count:\nCounting the frequency of characters in the string takes O(n), where n is the size of the input string s.\n\n##### Heap Operations:\n\n* Insertion into the heap: There are at most 26 characters (O(26) operations), so this is constant in practice.\n* Processing characters: \n    * Each character is pushed into and popped from the heap at most once per frequency.\n    * The cost of push and pop operations in a priority queue is O(log k), where k is the number of distinct characters (at most 26).\n    * In the worst case, the heap operations take O(n log k), where n is the total number of characters and k = 26.\n##### String Appending:\nAppending to the result string takes O(n) in total because the resulting string will have n characters.\n### Overall Time Complexity: `O(n+nlogk)=O(nlogk)`\n* Since k (number of distinct characters) is a small constant (26 for lowercase English letters), the complexity simplifies to O(n).\n\n### Space complexity:\n##### Frequency Array:\nThe vector<int> freq_vector uses O(26) = O(1) space.\n\n##### Priority Queue:\nThe priority queue can store up to k = 26 elements, so it uses O(k) = O(1) space.\n\n##### Result String:\nThe result string has a length of at most n, so it takes O(n) space.\n\nOverall Space Complexity: `O(n)`\n\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int repeatLimit) {\n        vector<int> freq_vector(26, 0);\n        for (int i = 0; i < s.size(); i++) {\n            freq_vector[s[i] - \'a\']++;\n        }\n        priority_queue<pair<int,int>> pq;\n        for(int i = 0; i < 26; i++){\n            if(freq_vector[i] > 0){\n                pq.push(make_pair(i,freq_vector[i]));\n            }\n        }\n        string result;\n        while(!pq.empty()){\n            pair<int,int> curr = pq.top();\n            pq.pop();\n\n            char curr_char = curr.first + \'a\' ;\n            int count = min(curr.second,repeatLimit);\n            curr.second -= count;\n            result.append(count,curr_char);\n\n            if(curr.second > 0){\n                if(pq.empty()) break;\n\n                pair<int,int> next = pq.top();\n                pq.pop();\n\n                char next_char = next.first + \'a\';\n                result.push_back(next_char);\n                next.second--;\n\n                if(next.second > 0){\n                    pq.push(next);\n                }\n                pq.push(curr);\n            }\n        }\n        return result;\n    }\n};\n```\n\n``` Java [Java]\nimport java.util.PriorityQueue;\n\nclass Solution {\n    public String repeatLimitedString(String s, int repeatLimit) {\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]); // Max-heap\n        for (int i = 0; i < 26; i++) {\n            if (freq[i] > 0) {\n                pq.offer(new int[]{i, freq[i]}); \n            }\n        }\n\n        StringBuilder result = new StringBuilder();\n\n        while (!pq.isEmpty()) {\n            int[] curr = pq.poll();\n            char currChar = (char) (\'a\' + curr[0]);\n            int count = Math.min(curr[1], repeatLimit);\n            curr[1] -= count;\n\n            for (int i = 0; i < count; i++) {\n                result.append(currChar);\n            }\n\n            if (curr[1] > 0) {\n                if (pq.isEmpty()) break;\n\n                int[] next = pq.poll();\n                char nextChar = (char) (\'a\' + next[0]);\n                result.append(nextChar); \n                next[1]--;\n\n                if (next[1] > 0) {\n                    pq.offer(next);\n                }\n                pq.offer(curr);\n            }\n        }\n\n        return result.toString();\n    }\n}\n```\n\n![Shinchan_upvote.jpg](https://assets.leetcode.com/users/images/8ea70382-a95e-4090-a4c3-c9b269b6955d_1734413458.8226507.jpeg)\n
['Array', 'String', 'Greedy', 'Heap (Priority Queue)', 'Counting', 'C++', 'Java']