Construct String With Repeat Limit

Leetcode Problem:

• Construct String With Repeat Limit

Summary

• Construct a new string using the characters of s such that no letter appears more than repeatLimit times in a row, and return the lexicographically largest possible string.

Approach

• The approach used is to first count the frequency of each character in s
• Then, we start with the largest possible character and keep adding it to the result string until we reach the repeatLimit limit
• If we encounter a character that is already at the limit, we remove the last occurrence of that character from the result string and replace it with the next character in the sorted order.

Complexity

• O(n log n) where n is the length of s, due to the sorting operation.

Solution Code:

class Solution {
public:
    vector arr;
    int charCnt[256];
    string repeatLimitedString(string s, int repeatLimit) {
        for(int i = 0 ; i < s.size(); i++){
            charCnt[s[i]]++;
        }
        for(int i = 'z'; i >= 'a'; i--){
            while(charCnt[i]--){
                arr.push_back(i);
            }
        }
        int repeat = 1;
        int beforeChar = arr[0];
        int j = 0;
        for(int i = 1 ; i < arr.size(); i++){
            if(beforeChar == arr[i]){
                repeat++;
            } else {
                repeat = 1;
                beforeChar = arr[i];
            }
            if(repeat > repeatLimit){
                if (j <= i){
                    j = i + 1;
                }
                while(j < arr.size() && beforeChar == arr[j]){
                    j++;
                }
                if(j >= arr.size()){
                    arr[i] = 0;
                    break;
                }
                char t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                beforeChar = arr[i];
                repeat = 1;
                j++;
            }
        }
        string ans = "";
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] == 0) break;
            ans += arr[i];
        }
        return ans;
    }
};