LeetCode 2182 - Construct String With Repeat Limit

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Heap (Priority Queue), Counting

Solution

Problem Understanding

The problem asks us to construct a string from the characters of a given string s under a specific constraint: no character can appear more than repeatLimit times consecutively. The goal is not just to create any valid string but to produce the lexicographically largest one possible. Lexicographic ordering is similar to dictionary order: a string is larger if its first differing character is later in the alphabet.

The input s is a string of lowercase English letters, and repeatLimit is an integer between 1 and the length of s. The constraints suggest that the input size can be up to 100,000 characters, so an efficient solution is required. Edge cases that could trip up a naive implementation include strings where one character dominates s, repeatLimit equals 1, or when the lexicographically largest character cannot be used consecutively because it hits the repeat limit.

The problem guarantees that s has at least one character, so we do not need to handle empty strings.

Approaches

A brute-force approach would attempt to generate all permutations of s, filter out those that violate the repeatLimit, and then pick the lexicographically largest. While correct in theory, this approach is computationally infeasible due to factorial time complexity (O(n!)) even for moderately sized inputs.

The optimal solution leverages a greedy strategy with a max-heap. The key observation is that to achieve the lexicographically largest string, we always want to place the largest available character while respecting the repeat limit. If the largest character reaches its consecutive repeat limit, we temporarily insert the next largest character to "break" the sequence, then resume using the largest character. By maintaining counts of each character, we can efficiently select which character to append next and how many times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generate all permutations, filter by repeat limit, pick largest
Optimal	O(n log k)	O(k)	Use max-heap with character counts; k ≤ 26 for lowercase letters

Algorithm Walkthrough

Count the frequency of each character in s using a hash map.
Push all characters with non-zero frequency into a max-heap (priority queue), sorted by the character value so that the largest character is on top.
Initialize an empty result string.
While the heap is not empty, pop the character with the highest value (currChar) and determine how many times it can be added consecutively without exceeding repeatLimit.
Append min(count[currChar], repeatLimit) instances of currChar to the result string.
If there are remaining instances of currChar, we must insert the next largest character to break the repetition. If the heap is empty at this point, we cannot append more of currChar.
Push back the remaining count of currChar into the heap if any.
Continue until the heap is empty.

Why it works: The algorithm maintains the invariant that the result string is always as lexicographically large as possible at each step. By using the largest available character until reaching the repeat limit and then temporarily inserting a smaller character, we respect the repeat limit while maximizing lexicographic order.

Python Solution

import heapq
from collections import Counter

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        count = Counter(s)
        # Use negative ASCII for max-heap
        max_heap = [(-ord(c), freq) for c, freq in count.items()]
        heapq.heapify(max_heap)
        
        result = []
        
        while max_heap:
            curr_char_ord, freq = heapq.heappop(max_heap)
            curr_char = chr(-curr_char_ord)
            use = min(freq, repeatLimit)
            
            result.extend([curr_char] * use)
            freq -= use
            
            if freq > 0:
                if not max_heap:
                    break  # cannot place any other char to break sequence
                next_char_ord, next_freq = heapq.heappop(max_heap)
                next_char = chr(-next_char_ord)
                result.append(next_char)
                next_freq -= 1
                if next_freq > 0:
                    heapq.heappush(max_heap, (next_char_ord, next_freq))
                heapq.heappush(max_heap, (curr_char_ord, freq))
        
        return ''.join(result)

In this Python implementation, the heap stores characters as negative ASCII values to simulate a max-heap using Python’s min-heap. The counter tracks remaining frequencies. The key logic is to append characters up to the repeat limit and break sequences with the next largest character when necessary.

Go Solution

package main

import (
    "container/heap"
)

type CharFreq struct {
    char rune
    freq int
}

type MaxHeap []CharFreq

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].char > h[j].char }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(CharFreq)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func repeatLimitedString(s string, repeatLimit int) string {
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    
    h := &MaxHeap{}
    heap.Init(h)
    for c, f := range freq {
        heap.Push(h, CharFreq{c, f})
    }
    
    result := []rune{}
    
    for h.Len() > 0 {
        curr := heap.Pop(h).(CharFreq)
        use := min(curr.freq, repeatLimit)
        for i := 0; i < use; i++ {
            result = append(result, curr.char)
        }
        curr.freq -= use
        
        if curr.freq > 0 {
            if h.Len() == 0 {
                break
            }
            next := heap.Pop(h).(CharFreq)
            result = append(result, next.char)
            next.freq--
            if next.freq > 0 {
                heap.Push(h, next)
            }
            heap.Push(h, curr)
        }
    }
    
    return string(result)
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

In Go, we use a custom max-heap implementation using container/heap since Go only provides a min-heap interface. Each character and its frequency are wrapped in a struct for heap storage. The logic mirrors the Python version, ensuring repeat limits are respected.

Worked Examples

Example 1: s = "cczazcc", repeatLimit = 3

Step	Heap State	Result	Explanation
1	z:2, c:4, a:1	""	Initialize max-heap by char descending
2	c:4, a:1	"zz"	Append 'z' 2 times (freq=2 < repeatLimit=3)
3	z:0, c:4, a:1	"zzc"	Append 'c' 3 times (limit)
4	c:1, a:1	"zzccc"	Next largest char 'a' to break sequence
5	c:1	"zzcccac"	Append remaining 'c' 1 time

Example 2: s = "aababab", repeatLimit = 2

Step	Heap State	Result	Explanation
1	b:3, a:4	""	Initialize heap
2	a:4	"bb"	Append 'b' 2 times (repeatLimit)
3	b:1, a:4	"bba"	Break sequence with 'a'
4	b:1, a:3	"bbabaa"	Append remaining 'b' and 'a' respecting limit

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log k)	Each character is pushed/popped from heap, n = length of string, k ≤ 26 characters
Space	O(k)	Heap stores at most 26 characters, plus counter and result string O(n)

The dominant factor is heap operations which are logarithmic in the number of unique characters, not the total length of s. Thus the solution scales efficiently to large strings.

Test Cases

# Provided examples
assert Solution().repeatLimitedString("cczazcc", 3) == "zzcccac"
assert Solution().repeatLimitedString("aababab", 2) == "bbabaa"

# Edge cases
assert Solution().repeatLimitedString("aaaaa", 1) == "a"  # only one 'a' can be consecutive
assert Solution().repeatLimitedString("abc", 2) == "cba"  # repeatLimit >= freq, just reverse sort
assert Solution().repeatLimitedString("aaabbbccc", 2) == "