Understand Construct String With Repeat Limit Problem

Problem Name: Construct String With Repeat Limit
Problem Description:

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"
Category:
  • Strings
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/construct-string-with-repeat-limit/description/?envType=daily-question&envId=2024-12-16

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
Main Function is not defined.
Helper Function:
public static String repeatLimitedString(String s, int repeatLimit) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
StringBuilder result = new StringBuilder();
int freq =1 
int pointer = chars.length -1;
for(int i = chars.length -1; i >= 0 ; i--){
if(result.length() > 0 && result.charAt(result.length() - 1) == chars[i]) {
if (freq < repeatLimit) {
result.append(chars[i]);
freq++;
}
else{
while ( pointer >= 0 && (chars[pointer] == chars[i] || pointer > i)) {
pointer--; 
}
if(pointer >= 0) {
result.append(chars[pointer]);
char temp = chars[i];
chars[i] = chars[pointer];
chars[pointer] = temp;
freq =1 ;
}
else{
break;
}
}
}
else{
result.append(chars[i]);
freq =1;
}
}
return result.toString();
}//function end
Utility Functions and Global variables:
Utility Function is not required.
Privacy Policy | About