2182. Construct String With Repeat Limit

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

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 01:

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        string result;
        vector<int> charFrequency(26);

        for (const char c : s)
            ++charFrequency[c - 'a'];

        while (true) {
            const bool isAddingSingleChar = !result.empty() && shouldAddOne(result, charFrequency);
            const int largestCharIndex = getLargestChar(result, charFrequency);

            if (largestCharIndex == -1){
                break;
            }

            const int numRepeats = isAddingSingleChar ? 1 : min(charFrequency[largestCharIndex], repeatLimit);
            result += string(numRepeats, 'a' + largestCharIndex);
            charFrequency[largestCharIndex] -= numRepeats;
        }

        return result;
    }

private:
    bool shouldAddOne(const string& result, const vector<int>& charFrequency) {
        for (int i = 25; i >= 0; --i)
            if (charFrequency[i]){
                return result.back() == 'a' + i;
            }
        return false;
    }

    int getLargestChar(const string& result, const vector<int>& charFrequency) {
        for (int i = 25; i >= 0; --i)
            if (charFrequency[i] && (result.empty() || result.back() != 'a' + i)){
                return i;
            }
                
        return -1;
    }
};

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        result = ""
        charFrequency = [0] * 26

        for c in s:
            charFrequency[ord(c) - ord('a')] += 1

        while True:
            isAddingSingleChar = result and self.shouldAddOne(result, charFrequency)
            largestCharIndex = self.getLargestChar(result, charFrequency)
            if largestCharIndex == -1:
                break
            numRepeats = 1 if isAddingSingleChar else min(charFrequency[largestCharIndex], repeatLimit)
            result += chr(ord('a') + largestCharIndex) * numRepeats
            charFrequency[largestCharIndex] -= numRepeats

        return result

    def shouldAddOne(self, result: str, charFrequency: list) -> bool:
        for i in range(25, -1, -1):
            if charFrequency[i]:
                return result[-1] == chr(ord('a') + i)
        return False

    def getLargestChar(self, result: str, charFrequency: list) -> int:
        for i in range(25, -1, -1):
            if charFrequency[i] and (not result or result[-1] != chr(ord('a') + i)):
                return i
        return -1

Time Complexity

• Frequency Calculation:
  • Calculating the frequency of characters in the input string s requires \(O(n)\), where \(n\) is the length of the string.
• Loop Iteration:
  • The outer while loop runs until all characters are added to the result, which can iterate at most \(O(n)\) times.
  • Each iteration of the loop involves:
    • Finding the largest character index (getLargestChar), which requires \(O(26)\) checks (constant time since there are 26 characters).
    • Checking if only one character should be added (shouldAddOne), which also requires \(O(26)\) checks.
  • The total cost of these operations is \(O(n \cdot 26) = O(n)\), since the constants can be ignored in asymptotic analysis.
• String Construction:
  • Constructing the result string involves appending characters, which takes \(O(n)\) in total across all iterations.
• Overall Time Complexity:

  The total time complexity is \(O(n)\), dominated by the operations on the string and frequency array.

Space Complexity

• Frequency Array:
  • The charFrequency array uses \(O(26) = O(1)\) space, as it has a fixed size of 26.
• Result String:
  • The result string result stores at most \(n\) characters, requiring \(O(n)\) space.
• Auxiliary Variables:
  • Temporary variables and constants used in the helper functions consume \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the result string.