Problelm: Construct String With Repeat Limit

Difficulty Medium

Description

You are given:

• A string s consisting of lowercase English letters.
• An integer repeatLimit.

Your task is to construct a new string repeatLimitedString using the characters of s, such that no letter appears more than repeatLimit times consecutively.

The goal is to return the lexicographically largest string possible.

Definitions:

• Lexicographically larger:
  • Compare strings by characters one by one from left to right.
  • A string a is larger than string b if:
    • At the first differing position, a has a character later in the alphabet.
    • If all characters match up to the shorter string, the longer string is larger.

Examples

Example 1:

Input:

s = "cczazcc"
repeatLimit = 3

Output:

"bbabaa"

Explanation:

• Steps:

  1. Sort the characters in s in descending order to maximize the lexicographical order:
     Sorted characters: z, z, c, c, c, c, a
  2. Start constructing the output string while ensuring no letter appears more than repeatLimit times consecutively.
  3. Add the letters in the following way:
     • Add 'z' → appears 2 times.
     • Add 'c' → appears 3 times.
     • Add 'a' → appears 1 time.
     • Add remaining 'c' → 1 time (to avoid breaking the repeatLimit rule).
  4. Final string:
     "zzcccac"

  Validation:

  • 'z' appears at most 2 times consecutively.
  • 'c' appears at most 3 times consecutively.
  • 'a' appears only 1 time.

The string "zzcccac" satisfies all conditions and is lexicographically largest.

Example 2:

Input:

s = "aaabbccc"       repeatLimit = 2

Output:

"ccbbaacc"