Construct String With Repeat Limit

Problem Statement

In this problem, you are provided with a string s and an integer repeatLimit. Your task is to construct a new string named repeatLimitedString from the characters of s. This construction must adhere to the condition where no single letter is repeated more than repeatLimit times consecutively. It's not mandatory to use all characters from the original string s. The goal of this task is to form the lexicographically largest repeatLimitedString that is possible under the given constraints.

To better understand, a string a is considered lexicographically larger than string b if at any position where they differ, the string a has a character that is later in the alphabet than the corresponding character in b. If their characters don't differ up to the shortest string's length, then the longer string is deemed larger.

Examples

Example 1

Input:

s = "cczazcc", repeatLimit = 3

Output:

"zzcccac"

Explanation:

We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2

Input:

s = "aababab", repeatLimit = 2

Output:

"bbabaa"

Explanation:

We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints

• 1 <= repeatLimit <= s.length <= 105
• s consists of lowercase English letters.

Approach and Intuition

1. Character Frequency Counting: First, count the frequency of each character in string s. This helps us understand how many times we can potentially use each character in the desired output string without violating the repeat limit.

2. Sorting and Priority: Since we need the lexicographically largest string, we should process the characters from the highest (e.g. z) to the lowest (e.g. a). Utilizing a max-heap (or sorting characters in reverse order) allows us to always pick the largest available character first.

3. Building the Result String: Start constructing the new string by repeatedly appending the largest available character:

   • Add the character up to repeatLimit times (or less if fewer are available).
   • If the same character cannot be used again immediately (because it would exceed the repeatLimit), introduce a different character (next largest available) to break the sequence.
   • Continue this pattern until no valid addition to the string is possible either because we run out of characters or can't add another character without violating the repeat limit.

4. Considerations for Lexicographical Order:

   • Always prioritize adding the highest possible character.
   • When forced to break a sequence (to adhere to the repeatLimit), choose the next highest character that doesn't violate the rules.

5. Edge Cases:

   • If repeatLimit is 1, you can't use the same character twice in a row, which essentially makes the result string an alternation of different characters.
   • High character frequency and a low repeatLimit might lead to unused characters.
   • Characters might need to be skipped if they risk creating violations of the repeatLimit even if they are lexicographically advantageous.

This structured approach ensures the lexicographically largest sequence possible while complying with the repeat limit constraints. With careful management of character selection and sequencing, the desired output can be achieved efficiently.

Solutions

class Solution {
public:
    string constructLimitedString(string str, int limit) {
        unordered_map<char, int> charCount;
        for (char c : str) {
            charCount[c]++;
        }
    
        priority_queue<char> characters;
        for (auto& [character, freq] : charCount) {
            characters.push(character);
        }
    
        string output;
        while (!characters.empty()) {
            char current = characters.top();
            characters.pop();
            int availableCount = charCount[current];
    
            int useCount = min(availableCount, limit);
            output.append(useCount, current);
    
            charCount[current] -= useCount;
    
            if (charCount[current] > 0 && !characters.empty()) {
                char nextCharacter = characters.top();
                characters.pop();
    
                output.push_back(nextCharacter);
                charCount[nextCharacter]--;
    
                if (charCount[nextCharacter] > 0) {
                    characters.push(nextCharacter);
                }
    
                characters.push(current);
            }
        }
    
        return output;
    }
};