✅ Easy to Understand | HashTable | Step by Step | Detailed Video Explanation🔥
IntuitionThe problem requires constructing a string such that no character repeats more than the given limit consecutively. My initial thought was to use a gree
# Intuition\nThe problem requires constructing a string such that no character repeats more than the given limit consecutively. My initial thought was to use a greedy approach, always selecting the lexicographically largest available character that respects the constraints, and falling back to smaller characters when necessary to break the repetition.\n\n# Approach\n1. Count the frequency of each character using an array of size 26 (one for each letter of the alphabet).\n2. Use a greedy strategy:\n   - Start with the largest available character.\n   - Append it to the result up to the repeat limit.\n   - If the character\'s frequency is not exhausted, find the next smaller character that can be appended to break the repetition.\n3. Continue until no more characters can be added while respecting the constraints.\n4. Return the constructed string.\n\n# Complexity\n- Time complexity:  \n  $$O(n + k)$$  \n  - $$O(n)$$ to count the frequency of characters, where $$n$$ is the length of the string.\n  - $$O(k)$$ for iterating through the characters in the array (at most 26 steps for the alphabet).\n\n- Space complexity:  \n  $$O(1)$$  \n  - Only a fixed-size frequency array of size 26 is used, regardless of the input size.\n\n\n# Code\n```java []\nclass Solution {\n    public String repeatLimitedString(String s, int repeatLimit) {\n        // Create a frequency array to count occurrences of each character in the string\n        int[] freq = new int[26];\n        for (char ch : s.toCharArray()) {\n            freq[ch - \'a\']++;\n        }\n\n        // StringBuilder to construct the resulting string\n        StringBuilder sb = new StringBuilder();\n        // Start from the largest character (\'z\') and move towards the smallest (\'a\')\n        int curr = 25;\n        while (curr >= 0) {\n            // Skip characters that are not present in the string\n            if (freq[curr] == 0) {\n                curr--;\n                continue;\n            }\n\n            // Append the current character up to the repeat limit\n            int limit = repeatLimit;\n            while (freq[curr] > 0 && limit > 0) {\n                sb.append((char) (\'a\' + curr));\n                freq[curr]--;\n                limit--;\n            }\n\n            // If the current character still has remaining frequency\n            if (freq[curr] > 0) {\n                // Find the next smaller character with a non-zero frequency\n                int smaller = curr - 1;\n                while (smaller >= 0 && freq[smaller] == 0) {\n                    smaller--;\n                }\n\n                // If no smaller character is found, break the loop\n                if (smaller < 0) {\n                    break;\n                }\n\n                // Append the smaller character to avoid exceeding the repeat limit\n                sb.append((char) (\'a\' + smaller));\n                freq[smaller]--;\n            }\n        }\n\n        // Return the constructed string\n        return sb.toString();\n    }\n}\n\n```\n```c++ []\n#include <string>\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    string repeatLimitedString(string s, int repeatLimit) {\n        vector<int> freq(26, 0);\n        for (char ch : s) {\n            freq[ch - \'a\']++;\n        }\n\n        string result;\n        int curr = 25;\n        while (curr >= 0) {\n            if (freq[curr] == 0) {\n                curr--;\n                continue;\n            }\n\n            int limit = repeatLimit;\n            while (freq[curr] > 0 && limit > 0) {\n                result += (char)(\'a\' + curr);\n                freq[curr]--;\n                limit--;\n            }\n\n            if (freq[curr] > 0) {\n                int smaller = curr - 1;\n                while (smaller >= 0 && freq[smaller] == 0) {\n                    smaller--;\n                }\n                if (smaller < 0) {\n                    break;\n                }\n                result += (char)(\'a\' + smaller);\n                freq[smaller]--;\n            }\n        }\n\n        return result;\n    }\n};\n```\n```python []\nclass Solution:\n    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n        # Frequency array for counting occurrences of each character\n        freq = [0] * 26\n        for ch in s:\n            freq[ord(ch) - ord(\'a\')] += 1\n\n        result = []\n        curr = 25\n        while curr >= 0:\n            if freq[curr] == 0:\n                curr -= 1\n                continue\n\n            # Append the current character up to the repeat limit\n            limit = repeatLimit\n            while freq[curr] > 0 and limit > 0:\n                result.append(chr(curr + ord(\'a\')))\n                freq[curr] -= 1\n                limit -= 1\n\n            # If the current character still has remaining frequency\n            if freq[curr] > 0:\n                # Find the next smaller character with a non-zero frequency\n                smaller = curr - 1\n                while smaller >= 0 and freq[smaller] == 0:\n                    smaller -= 1\n\n                # If no smaller character is found, break\n                if smaller < 0:\n                    break\n\n                # Append the smaller character to avoid exceeding the repeat limit\n                result.append(chr(smaller + ord(\'a\')))\n                freq[smaller] -= 1\n\n        return \'\'.join(result)\n\n```\n\n\nLeetCode 2182 Construct String With Repeat Limit | HashTable | Greedy | Asked in Microsoft\nhttps://youtu.be/19hUSyLOZag
['Hash Table', 'String', 'Greedy', 'Java']