Java | O(n) | No map or queue | Beats > 95%
Intuition\n Describe your first thoughts on how to solve this problem. \nCreate a frequency count array for all letters in the input string. Iterate over the fr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCreate a frequency count array for all letters in the input string. Iterate over the frequency count array from the count of `z` to `a`. Skip the letters for which the count is `0`. Append one letter at a time to the output string till the frequency count of the letter becomes `0` or the repeat limit is reached. If the repeat limit is reached, remember the letter\'s index, move on to the next lexicographically largest letter and append a single instance of that, then move back to the remembered letter and continue the procees as normal.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build a frequency count array for all letters in the input string `s`.\n2. Iterate through the frequency count array from the index of `z` to `a`.\n3. Skip any letter for which the frequency is `0`.\n4. Append one instance of the letter at a time to the output string till the frequency of the letter becomes `0` or the repeat limit is reached.\n5. If the repeat limit is reached and the frequency of the letter is > 0, remember the letter\'s index and move on to the next iteration.\n6. In each iteration, check if there\'s a remembered letter. If yes, append a single instance of the current letter to the output string and skip back to the remembered letter\'s index. Then continue the process as normal.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  public String repeatLimitedString(String s, int repeatLimit) {\n    int[] freq = new int[26];\n\n    for (char c : s.toCharArray())\n      freq[c - \'a\']++;\n\n    int pendingLetterIndex = -1;\n    StringBuilder sb = new StringBuilder();\n\n    for (int i=25; i >= 0; i--) {\n      if (freq[i] == 0)\n        continue;\n\n      if (pendingLetterIndex > 0) {\n        // A lexicographically larger letter is still avaialble.\n        // Append a single instance of the current letter and move\n        // back to the remembered letter.\n\n        sb.append((char)(\'a\' + i));\n        freq[i]--;\n        i = pendingLetterIndex;\n        pendingLetterIndex = -1;\n      } else {\n        for (int j=0; j < repeatLimit && freq[i] > 0; j++, freq[i]--)\n          sb.append((char)(\'a\' + i));\n\n        // Repeat limit reached, remember to get back to this letter.\n        if (freq[i] > 0)\n          pendingLetterIndex = i+1;\n      }\n    }\n    return sb.toString();\n  }\n}\n```
['String', 'Greedy', 'Counting', 'Java']