LeetCode Solutions Blog

Construct String With Repeat Limit

Difficulty: Medium

Problem Description

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s. Return the lexicographically largest repeatLimitedString possible.

Key Insights

The goal is to construct a string that adheres to the repeat limit while being lexicographically largest.
Using a max-heap (or priority queue) allows us to always access the largest character available.
If the largest character exceeds the repeat limit, we need to insert a smaller character in between to maintain the structure.
We can count the occurrences of each character to facilitate the construction of the output string.

Space and Time Complexity

Time Complexity: O(n log k), where n is the length of the input string and k is the number of unique characters.
Space Complexity: O(k), where k is the number of unique characters for the heap and character count storage.

Solution

To solve the problem, we can use a greedy approach with a max-heap to prioritize the largest characters. We will count the occurrences of each character and store them in the heap. While constructing the result string, we will ensure that no character exceeds the repeatLimit by placing a different character in between if necessary.

Code Solutions

import heapq
from collections import Counter

def repeatLimitedString(s: str, repeatLimit: int) -> str:
    # Count the occurrences of each character
    count = Counter(s)
    # Create a max-heap based on characters
    max_heap = [(-ord(char), char, count[char]) for char in count]
    heapq.heapify(max_heap)
    
    result = []
    
    while max_heap:
        # Get the largest character available
        char_code, char, freq = heapq.heappop(max_heap)
        use_count = min(freq, repeatLimit)
        
        # Add the character to the result
        result.append(char * use_count)
        
        # Reduce frequency
        freq -= use_count
        
        # If the frequency is still positive, we need to handle placement
        if freq > 0:
            if max_heap:  # Check if we can place another character
                next_char_code, next_char, next_freq = heapq.heappop(max_heap)
                result.append(next_char)  # Place the next largest character
                next_freq -= 1  # Reduce its frequency

                # If the next character still has remaining frequency, push it back to heap
                if next_freq > 0:
                    heapq.heappush(max_heap, (next_char_code, next_char, next_freq))

                # Push the original character back to heap
                heapq.heappush(max_heap, (char_code, char, freq))
            else:
                break  # No valid placement possible
            
        # If there are remaining characters, push it back to the heap
        elif freq > 0:
            heapq.heappush(max_heap, (char_code, char, freq))

    return ''.join(result)