Python | Greedy Algorithm & Priority Queue
see the Successfully Accepted SubmissionCodeSteps:

Frequency Count:
Use a Counter to count the frequency of each character in the string.


Max Heap:
Use a max
[see the Successfully Accepted Submission](https://leetcode.com/problems/construct-string-with-repeat-limit/submissions/1480683191/?envType=daily-question&envId=2024-12-17)\n\n# Code\n```python3 []\nclass Solution:\n    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n        # Count frequencies of each character\n        freq = Counter(s)\n        \n        # Use a max heap (negative frequencies for max heap simulation)\n        max_heap = []\n        for char, count in freq.items():\n            heapq.heappush(max_heap, (-ord(char), count))  # Store (negative ASCII value, count)\n        \n        result = []  # Final result list\n        while max_heap:\n            # Extract the largest character\n            neg_char, count = heapq.heappop(max_heap)\n            char = chr(-neg_char)\n            \n            # Determine how many times we can use this character (up to repeatLimit)\n            use_count = min(count, repeatLimit)\n            result.extend([char] * use_count)\n            \n            count -= use_count  # Remaining count after usage\n            \n            if count > 0:  # If there are more of this character left\n                if not max_heap:\n                    break  # No other characters to use, we are done\n                    \n                # Extract the second largest character to "break" the sequence\n                neg_next_char, next_count = heapq.heappop(max_heap)\n                next_char = chr(-neg_next_char)\n                \n                # Use the second largest character once to break the sequence\n                result.append(next_char)\n                next_count -= 1  # Update the count\n                \n                # Push both characters back into the heap if they still have remaining counts\n                heapq.heappush(max_heap, (neg_char, count))\n                if next_count > 0:\n                    heapq.heappush(max_heap, (neg_next_char, next_count))\n        \n        # Join the list into the final string\n        return "".join(result)\n\n```\n\n## Steps:\n1. **Frequency Count**:  \n   Use a `Counter` to count the frequency of each character in the string.\n\n2. **Max Heap**:  \n   Use a max heap (priority queue) to always extract the lexicographically largest character.  \n   - In Python, we simulate a max heap using **negative frequencies**.\n\n3. **Construct the String**:  \n   - Repeatedly pick the largest character while respecting the `repeatLimit`.  \n   - If the `repeatLimit` for the current character is reached, temporarily use the next largest character to *break* the sequence and then return to the largest character.\n\n4. **Edge Cases**:  \n   If it is impossible to continue constructing the string (e.g., no more characters are available to "break" a sequence), stop.\n\n---\n\n## Explanation of Key Steps:\n\n### 1. **Heap Initialization**  \n- Each character\'s negative ASCII value and count are pushed into the heap.  \n- This ensures the lexicographically largest characters are prioritized.\n\n### 2. **Constructing the String**  \n- While the heap is not empty:  \n  - Extract the largest character and use it up to `repeatLimit` times.  \n  - If there are still more occurrences of this character left, use the **second largest character** to *break* the consecutive sequence.\n\n### 3. **Reinserting Characters**  \n- Both the largest and second largest characters are reinserted back into the heap if they have remaining occurrences.\n\n### 4. **Stopping Condition**  \n- If there are no other characters to "break" the sequence, the process ends.\n\n---\n\n## Complexity Analysis:\n\n### Time Complexity:\n- Pushing and popping from the heap takes \\( O(\\log k) \\), where \\( k \\) is the number of distinct characters.  \n- Each character in the string is processed once, so the overall time complexity is \\( O(n \\log k) \\), where \\( n \\) is the length of the string.\n\n### Space Complexity:\n- The heap stores at most \\( O(k) \\) characters, and the result list takes \\( O(n) \\) space.  \n- Therefore, the overall space complexity is \\( O(n + k) \\).\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']