Largest String With a Run Cap

Medium

You get a bag of letters as the string letters and a number max_run. Build a new string from these letters in which no letter repeats more than max_run times in a row. You do not have to use every letter, but each letter of letters can be used at most once. Return the lexicographically largest such string. String a is larger than b if, at the first position where they differ, a has the letter later in the alphabet; if one string is a prefix of the other, the longer one is larger.

Example 1

letters="yxyyy", max_run=2 → 'yyxyy'

We would like all four y in a row, but at most two are allowed. So we get yy, then x as a separator, then the remaining yy: "yyxyy".

Example 2

letters="cccca", max_run=1 → 'cac'

Every c needs a separator after it, and there is only one, a. The result is "cac"; the remaining c letters cannot be used.

Example 3

letters="bab", max_run=3 → 'bba'

Constraints

1 ≤ max_run ≤ len(letters) ≤ 10⁵
letters consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Hash Table String Counting Heap (Priority Queue)

Similar problems

No Twin Letters Side by Side Medium Fill the Blanks With the Fewest Repeats Medium Equal Letters Kept Apart Hard Characters Grouped by Count Medium Jobs With a Cooldown Medium

Input

letters="yxyyy", max_run=2

Expected

'yyxyy'

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.