You're given a string s of lowercase English letters and an integer repeatLimit. Build a new string out of the letters of s such that no letter appears more than repeatLimit times in a row. You may use each letter at most as many times as it appears in s, and you don't have to use all of them.
Return the lexicographically largest string you can build this way.
A string a is lexicographically larger than a string b if, at the first position where they differ, a has the letter that comes later in the alphabet. If one string is a prefix of the other, the longer one is larger.
Examples
Example 1
Input: s = "zzzzzy", repeatLimit = 2
Output: "zzyzz"
After two zs the run has to be broken, and y is the only other letter. That allows two more zs. The last z can't be placed — there is nothing left to separate it from the previous run.
Example 2
Input: s = "qqqqqqpp", repeatLimit = 2
Output: "qqpqqpqq"
Each p is spent breaking up the qs, which lets all six qs be used.
Example 3
Input: s = "abc", repeatLimit = 1
Output: "cba"
Example 4
Input: s = "aaaa", repeatLimit = 2
Output: "aa"
Only one kind of letter, so the string stops after the first run.
Example 5
Input: s = "banana", repeatLimit = 1
Output: "nbna"
n goes first, then b separates the two ns. After that only as remain, and just one of them can be used.
Constraints
1 <= repeatLimit <= s.length <= 10^5sconsists of lowercase English letters.