Greedy make_heap+ C-array vs priority_queue
IntuitionAgain Greedy heap with k operations where k= # of of diffrent chars.
Similar process is done by used priority_queue. 2 approaches have slight different
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAgain Greedy heap with k operations where k= # of of diffrent chars.\nSimilar process is done by used priority_queue. 2 approaches have slight different processes for the 2nd max character.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. count `freq`\n2. build `heap` with char with freq>0\n3. Use `make_heap`\n4. While the `heap` is not empty, i.e. hz>0 do the following:\n```\npop_heap(heap, heap + hz);\nchar c= heap[hz-1];\nhz--;// pop\n\nint& f=freq[c-\'a\']; \nint use=min(f, k); // Add as many characters as possible (up to k)\nans.append(use, c);\nf-= use;\n\nif (f > 0 && hz > 0) {\n    // Use the next character to interleave\n    pop_heap(heap, heap+hz);\n    char c2=heap[hz-1];\n    hz--;// pop\n\n    ans.push_back(c2);\n    int& f2 = freq[c2-\'a\'];\n    f2--;\n\n    // Reinsert both characters back \n    if (f2 > 0) {\n        heap[hz++]=c2;// push c2\n        push_heap(heap, heap + hz);\n    }\n    heap[hz++] = c; // push c\n    push_heap(heap, heap + hz);\n} \n```\n5. return `ans`\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nmake_heap: $$O(n\\log k)$$\npriority_queue: $O((n+k)\\log n)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code Greedy heap\n```cpp [C++ heap]\nclass Solution {\npublic:\n    static string repeatLimitedString(string& s, int k) {\n        int freq[26]={0}, hz=0;\n\n        // Count frequency\n        for (char c : s) \n            freq[c-\'a\']++;\n        \n        // Use C-array to act as max heap\n        char heap[26];\n        for (int i = 0; i < 26; i++) {\n            if (freq[i]> 0) \n                heap[hz++]=\'a\'+ i;\n        }\n        make_heap(heap, heap+hz);\n\n        string ans;\n        ans.reserve(s.size());\n\n        while (hz > 0) {\n            pop_heap(heap, heap + hz);\n            char c= heap[--hz];\n\n            int& f=freq[c-\'a\'];\n            int use=min(f, k); // Add as many characters as possible (up to k)\n            ans.append(use, c);\n            f-= use;\n\n            if (f > 0 && hz > 0) {\n                // Use the next character to interleave\n                pop_heap(heap, heap+hz);\n                char c2=heap[--hz];\n\n                ans.push_back(c2);\n                int f2 =--freq[c2 - \'a\'];\n\n                // Reinsert both characters back \n                if (f2 > 0) {\n                    heap[hz++]=c2;\n                    push_heap(heap, heap + hz);\n                }\n                heap[hz++] = c;\n                push_heap(heap, heap + hz);\n            } \n        }\n        return ans;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# C++ using priority_queue\n```cpp [C++ priority queue]\nclass Solution {\npublic:\n    static string repeatLimitedString(string& s, int k) {\n        int freq[26] = {0};\n        // Count frequency\n        for (char c : s) \n            freq[c-\'a\']++;\n        \n        // Use a max-heap to hold char\n        priority_queue<char> pq;\n        for (int i=0; i<26; i++) {\n            if (freq[i] > 0) \n                pq.emplace(\'a\'+i);\n        }\n        \n        string ans;\n        ans.reserve(s.size());\n                \n        while (!pq.empty()) {\n            char c=pq.top();\n            pq.pop();\n            \n            // Add as many characters as possible (up to k)\n            int& f=freq[c-\'a\'];\n            int use = min(f, k);\n            ans.append(use, c);\n            f-= use;\n\n            if (f > 0) {\n                if (pq.empty()) \n                    break; // No other character to interleave\n                \n                // Use the next character in priority queue to interleave\n                char c2= pq.top();\n                ans.push_back(c2);\n                int f2=--freq[c2-\'a\'];\n\n                if (f2==0) pq.pop();\n\n                // Re-add the original character \n                pq.emplace(c);\n            }\n        }\n        \n        return ans;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['String', 'Greedy', 'Heap (Priority Queue)', 'C++']