✅✅easy and beginner friendly solution 🔥🔥
Intuition
The goal is to construct the lexicographically largest string such that no character appears more than repeatLimit times consecutively. To achieve thi
Intuition\nThe goal is to construct the lexicographically largest string such that no character appears more than repeatLimit times consecutively. To achieve this, we prioritize the largest characters (lexicographically) and use a greedy approach to add them to the result. If a character reaches the repeatLimit, we temporarily switch to the next largest character to break the consecutive streak.\n\nApproach\nCount Frequencies: Use a frequency array v of size 26 to count occurrences of each character in the input string s.\n\nMax-Heap: Create a max-heap (priority queue) where each element is a pair {char_index, frequency}. Characters with higher lexicographical value will have higher priority because the heap sorts in descending order.\n\nGreedy Character Insertion:\n\nExtract the character with the largest lexicographical value (curr) from the heap.\nAppend it to the result up to repeatLimit times or its remaining frequency, whichever is smaller.\nIf the character still has leftover occurrences, temporarily switch to the next largest character (next) to avoid violating the repeatLimit condition.\nAppend one occurrence of next to the result and push the updated curr and next back into the heap.\nRepeat Until Heap is Empty: Continue this process until the heap is empty or no valid characters can be inserted.\n\nComplexity\nTime Complexity:\n- The time complexity is \nO(nlog26), where \n\uD835\uDC5B\nn is the length of the string s.\n\nConstructing the frequency array takes \nO(n).\nPushing and popping from the heap takes \nO(log26), and since there are only 26 letters, the logarithm becomes constant.\n- Space Complexity:\nO(26)=O(1) because we use a fixed-size frequency array and heap.\n\n\n\n# Code\n```cpp []\n#include <string>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int repeatLimit) {\n        vector<int> v(26, 0);\n        for (int i = 0; i < s.size(); i++) v[s[i] - \'a\']++;\n\n        priority_queue<pair<int, int>> maxheap;\n        for (int i = 0; i < 26; i++) \n            if (v[i] > 0) maxheap.push({i, v[i]});\n\n        string result = "";\n\n        while (!maxheap.empty()) {\n            auto curr = maxheap.top();\n            maxheap.pop();\n\n            char curr_char = \'a\' + curr.first;\n            int count = min(curr.second, repeatLimit);\n            result.append(count, curr_char);\n            curr.second -= count;\n\n            if (curr.second > 0) {\n                if (maxheap.empty()) break;\n\n                auto next = maxheap.top();\n                maxheap.pop();\n\n                char next_char = \'a\' + next.first;\n                result.push_back(next_char);\n                next.second--;\n\n                if (next.second > 0) maxheap.push(next);\n                maxheap.push(curr);\n            }\n        }\n        return result;\n    }\n};\n\n\n\n\n\n
['Hash Table', 'String', 'Heap (Priority Queue)', 'C++']