LeetCode Solutions Blog

Construct String With Repeat Limit

Number: 2300

Difficulty: Medium

Paid? No

Problem Description

Given a string s and an integer repeatLimit, construct the lexicographically largest string possible using the characters from s such that no character appears more than repeatLimit times consecutively. You do not have to use all characters from s.

Key Insights

Use a frequency count for each character in s.
Process characters in descending lexicographical order (from 'z' to 'a').
Greedily append each character up to the limit set by repeatLimit.
When the current character is about to exceed the allowed consecutive count, insert the next available lower character to break the sequence.
Repeat the process until no valid characters remain to be inserted.

Space and Time Complexity

Time Complexity: O(n + 26) ≈ O(n), where n is the length of s. Space Complexity: O(26) = O(1), which is used for the frequency count.

Solution

Maintain an array of counts for the 26 lowercase letters. Start by picking the lexicographically largest available character and add it repeatedly up to repeatLimit. If occurrences remain, find the next smaller character to insert as a break between consecutive groups. If no such character exists, the process terminates. This greedy approach ensures that the result is the lexicographically largest valid string that meets the repeat limit requirement.

Code Solutions

# Python solution for constructing the lexicographically largest string with a repeat limit

def repeatLimitedString(s: str, repeatLimit: int) -> str:
    # Frequency count for each lowercase English letter
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord('a')] += 1
        
    result = []  # Use list for efficient string building
    curr = 25  # Start with 'z'
    while curr >= 0:
        if counts[curr] == 0:
            curr -= 1
            continue
        # Determine how many times we can append the current character
        use = min(counts[curr], repeatLimit)
        result.append(chr(curr + ord('a')) * use)
        counts[curr] -= use
        
        # If current character still has remaining occurrences, we need to break the consecutive sequence
        if counts[curr] > 0:
            next_char = curr - 1
            # Find the next lower character available
            while next_char >= 0 and counts[next_char] == 0:
                next_char -= 1
            if next_char < 0:
                break  # No available character to break the sequence, so we are done
            result.append(chr(next_char + ord('a')))
            counts[next_char] -= 1
        else:
            curr -= 1  # Move to next character if fully used
    return "".join(result)

# Example usage
print(repeatLimitedString("cczazcc", 3))  # Expected output: "zzcccac"
print(repeatLimitedString("aababab", 2))  # Expected output: "bbabaa"