Construct String with Repeat Limit - Easy Explanation - Unique Solution👌🔜
IntuitionWe have to reorder the given string into lexicographically longer string so that the number of repeated element in a row should be atmost repeatLimit.H
# Intuition\nWe have to reorder the given string into lexicographically longer string so that the number of repeated element in a row should be atmost repeatLimit.\n\nHence this can be computed by noting frequency of all the characters in the string.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n**Pre-requirements**:\n\nInitialize freq array of size 26 and the datatype int to have the count of each character in the String s.\n\n    int[] freq=new int[26];\n\nIterate through all the characters in a String s and increment the freq count by freq[ch-\'a\'].Since each character is at index ch-\'a\'.\n\n    for(char ch:s.toCharArray())\n    {\n        freq[ch-\'a\']++;\n    }\n\n**Construct the character array**:\n\nInitialize the character array str to be the length of the string s.\n\n    char[] str=new char[s.length()];\n\nInitialize the wriIndex to be 0.Then iterate over all the elements of a frequency array.\n\n    int wriIndex=0;\n    for(int i=25;i>=0;i--){\n\nIterate through the value of the freq array ,freq[i] times.Construct a string by adding character as (char)(i+\'a\').\n\n    for(int j=0;j<freq[i];j++)\n    {\n        str[wriIndex++]=(char)(i+\'a\'); \n    }\n\n**Important Intialization for checking condition**:\n\nInitialize rep to be 0 to keep track of number of repeated characters in a row, cur to hold the character at the 0-th index,and next to be 1.\n\n    int rep=0;\n    char cur=str[0];\n    int next=1;\n\nIterate through all the characters of the character array str.\n\n    for (int i = 0; i < str.length; i++) {\n\nIf str[i]==cur, then increment the rep variable and if rep==repeatLimit+1, then also check if the next<i , if so increment next by i+1.\n\n    if (str[i] == cur) {\n        rep++;\n        if (rep == repeatLimit + 1) {\n            if (next < i) next = i + 1;\n\nContinuously iterate through till next is less than the str length and str[next]=cur , then increment the next.\n\n    while (next < str.length && str[next] >= cur) next++;\n\nIf next equals the length of the character array str, then return the value of string as str from index 0 to i.\n\n    if (next == str.length) return String.valueOf(str, 0, i);\n\nSwap str[i] and the character str[next] with the use of tmp character, then in the new iteration-> rep is again set to 0.\n\n    char tmp = str[i];\n    str[i] = str[next];\n    str[next] = tmp;\n    rep = 0;\n\nIf the rep is not equal to repeatLimit+1 , then set the cur as str[i] and rep is set as 1.\n\n    else {\n    cur = str[i];\n    rep = 1;\n    }\n\n**Returning the value**:\n\nReturn the string by converting the given character array into string by the String.valueOf(str).\n\n    return String.valueOf(str);\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- ***Time complexity***: **O(n)**.\n    n -> number of characters in the string s.\n\n**Frequency array population**: **O(n)**.\nThe for loop iterates over all characters in the string s.Hence it takes O(n) time.\n\n**Building the str character array**: **O(n)**.\nThe nested loops iterate over the freq array (of size 26) and populate the str array.\n\nIn the worst case, all characters in s are used, so it takes \n**O(n) time**.\n\n**Rearranging character(for loop)**: **O(n)**.\nThe loop processes the str array, which has **O(n) characters**.\n \nThe inner while loop that adjusts next depends on how many times we **skip characters**.\n \nIn the worst case, next traverses the rest of the string, but since characters are only skipped once, the total work is **O(n) time**.\n\n**Total Time Complexity**: **O(n)**.\n\nOverall Time Complexity is the time complexity due to all **3 loops**,hence it\'s time complexity is **O(n)+O(n)+O(n) = O(n) time**.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity***: **O(n)**.\n    n -> number of characters in the string s.\n\n**Frequency array (freq)**: **O(1)**.\n    It stores fixed size of **26 characters** and hence it occupies only **constant space, O(1)**.\n\n**Character Array(str)**: **O(n)**.\nThe space occupied by the character array is proportional to the number of characters in the string s.Hence it takes **O(n) space**.\n\n**Total Space Complexity**: **O(1)**.\nHence the overall space complexity is dominated by the character array, **str**. Hence it takes **O(n) space**.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public String repeatLimitedString(String s, int repeatLimit) {\n        //repeatLimitedString using chars of s \n        // no letter appears more than repeatLimit times in a row\n        //do not have to use all the characters from s\n        int[] freq=new int[26];\n        for(char ch:s.toCharArray())\n        {\n            freq[ch-\'a\']++;\n        }\n        char[] str=new char[s.length()];\n\n        int wriIndex=0;\n        for(int i=25;i>=0;i--)\n        {\n            for(int j=0;j<freq[i];j++)\n            {\n              str[wriIndex++]=(char)(i+\'a\'); \n            }\n        }\n        int rep=0;\n        char cur=str[0];\n        int next=1;\n         for (int i = 0; i < str.length; i++) {\n            if (str[i] == cur) {\n                rep++;\n                if (rep == repeatLimit + 1) {\n                    if (next < i) next = i + 1;\n                    while (next < str.length && str[next] >= cur) next++;\n                    if (next == str.length) return String.valueOf(str, 0, i);\n                    char tmp = str[i];\n                    str[i] = str[next];\n                    str[next] = tmp;\n                    rep = 0;\n                }\n            } else {\n                cur = str[i];\n                rep = 1;\n            }\n        }\n        return String.valueOf(str);\n    }\n}\n```
['String', 'Counting', 'Java']