Sorted Hash Map Python | Beats 99% 😎🐍
IntuitionThe problem requires constructing a string using characters from s such that:
No letter appears more than repeatLimit times consecutively.
The resultin
## **Intuition**\nThe problem requires constructing a string using characters from `s` such that:\n1. No letter appears more than `repeatLimit` times consecutively.\n2. The resulting string is lexicographically the largest possible.\n\nThe lexicographical order constraint suggests that we should prioritize using larger characters first (characters later in the alphabet) while ensuring the `repeatLimit` condition is not violated.\n\n---\n\n## **Approach**\n1. **Count Character Frequencies**:  \n   Use `Counter` to get the frequency of each character in `s`.  \n   \n2. **Sort Characters**:  \n   Sort the character-frequency pairs in reverse lexicographical order so that larger characters come first.\n\n3. **Build the Result String**:  \n   - Start constructing the string by greedily taking as many instances of the largest available character as allowed (up to `repeatLimit`).\n   - If the current largest character exceeds `repeatLimit`, insert a single instance of the next largest character to "break" the repetition, and then continue adding the first character.\n   - If no second-largest character is available to break the sequence, terminate the process.\n\n4. **Edge Cases**:  \n   Handle the scenario where a character\'s frequency is exhausted (`pop` it from the list).\n\n---\n\n## **Complexity**\n\n### Time Complexity:\n- **Counting Frequencies**: \\(O(n)\\), where \\(n\\) is the length of `s`.\n- **Sorting Characters**: \\(O(26 \\log 26)\\) \u2192 effectively \\(O(1)\\) since there are at most 26 unique lowercase letters.\n- **Building the Result String**: \\(O(n)\\), as we iterate through all characters to construct the output.\n\nOverall time complexity: **$$ O(n) $$**\n\n\n### Space Complexity:\n- \\(O(26) = O(1)\\) for the `Counter` and sorted list of characters.\n- \\(O(n)\\) for the resulting string `repeatLimitedString`.\n\nTotal space complexity: **$$ O(n) $$**\n\n---\n\n## **Code**\n```python\nfrom collections import Counter\n\nclass Solution:\n    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n        # Step 1: Count character frequencies and sort by lexicographical order (descending)\n        char_freq = [list(i) for i in Counter(s).items()]\n        char_freq.sort(reverse=True)  # Sort by character (key) in descending order\n        \n        result = ""  # Resultant string\n\n        while char_freq:\n            if char_freq[0][1] > repeatLimit:\n                # Append repeatLimit of the largest available character\n                result += char_freq[0][0] * repeatLimit\n                char_freq[0][1] -= repeatLimit\n\n                # If possible, append the next largest character to "break" the limit\n                if len(char_freq) > 1:\n                    result += char_freq[1][0]\n                    char_freq[1][1] -= 1\n                    if char_freq[1][1] == 0:\n                        char_freq.pop(1)  # Remove if exhausted\n                else:\n                    break  # No other character to use, terminate\n            else:\n                # Append all remaining occurrences of the largest available character\n                result += char_freq[0][0] * char_freq[0][1]\n                char_freq.pop(0)  # Remove as frequency is exhausted\n            \n        return result\n
['Hash Table', 'Greedy', 'Counting', 'Counting Sort', 'Python3']