Construct String With Repeat Limit - Practice Coding Problems

Construct String With Repeat Limit - Problem

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.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Input & Output

Example 1 — Basic Case

$ Input: s = "cczazcc", repeatLimit = 3

› Output: "zzcccacc"

💡 Note: Start with largest character 'z' (appears 2 times), then 'c' (3 times max), then use 'a' as separator, then remaining 'c'.

Example 2 — Repeat Limit Hit

$ Input: s = "aababab", repeatLimit = 2

› Output: "bbabaa"

💡 Note: Use 'b' twice, then 'a' as separator, then 'b' once, then remaining 'a' characters.

Example 3 — Single Character Type

$ Input: s = "aaaa", repeatLimit = 2

› Output: "aa"

💡 Note: Only one character type available, use up to repeat limit and stop (no separator available).

Constraints

1 ≤ s.length ≤ 10⁵
1 ≤ repeatLimit ≤ 10⁴
s consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "cczazcc" with repeatLimit = 3

Greedy Construction

Use largest characters first, respecting repeat limit

Final Result

Lexicographically largest valid string

Key Takeaway

🎯 Key Insight: Always use the largest available character up to the repeat limit, then use the next largest as a separator when needed.

Asked in

G Google 28 a Amazon 23 f Facebook 15 M Microsoft 12

The key insight is to greedily use the largest available character while respecting the repeat limit, using the next largest as separator when needed. Best approach uses frequency counting with greedy construction for optimal performance. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Max Heap Priority Queue	O(n + k log k)	O(k)	Use a max heap to always get the largest available character while tracking counts
Frequency Count + Greedy Construction	O(n)	O(1)	Count character frequencies and greedily build result using largest characters first
Brute Force - Generate All Permutations	O(n!)	O(n!)	Generate all valid permutations and find the lexicographically largest one

Max Heap Priority Queue — Algorithm Steps

Step 1: Build max heap with character frequencies
Step 2: Extract largest character and use up to repeat limit
Step 3: If more of same character needed, use second largest as separator
Step 4: Continue until heap is empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Max Heap

Create heap with character frequencies ordered by lexicographical value

Extract & Use

Always extract largest character and use up to repeat limit

Separator Logic

When repeat limit hit, use second largest as separator

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int freq;
} CharFreq;

typedef struct {
    CharFreq* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int capacity) {
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->data = malloc(capacity * sizeof(CharFreq));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(CharFreq* a, CharFreq* b) {
    CharFreq temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MaxHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->data[parent].ch >= heap->data[index].ch) break;
        swap(&heap->data[parent], &heap->data[index]);
        index = parent;
    }
}

void heapifyDown(MaxHeap* heap, int index) {
    while (1) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && heap->data[left].ch > heap->data[largest].ch) {
            largest = left;
        }
        if (right < heap->size && heap->data[right].ch > heap->data[largest].ch) {
            largest = right;
        }
        
        if (largest == index) break;
        swap(&heap->data[index], &heap->data[largest]);
        index = largest;
    }
}

void push(MaxHeap* heap, CharFreq item) {
    heap->data[heap->size] = item;
    heapifyUp(heap, heap->size);
    heap->size++;
}

CharFreq pop(MaxHeap* heap) {
    CharFreq result = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return result;
}

char* solution(char* s, int repeatLimit) {
    int len = strlen(s);
    
    // Count character frequencies
    int freq[26] = {0};
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    // Create max heap
    MaxHeap* heap = createHeap(26);
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            CharFreq cf = {'a' + i, freq[i]};
            push(heap, cf);
        }
    }
    
    char* result = malloc((len + 1) * sizeof(char));
    int resultLen = 0;
    
    while (heap->size > 0) {
        // Get the largest character
        CharFreq first = pop(heap);
        
        // Use up to repeatLimit of this character
        int use = (first.freq < repeatLimit) ? first.freq : repeatLimit;
        for (int i = 0; i < use; i++) {
            result[resultLen++] = first.ch;
        }
        first.freq -= use;
        
        // If we still have more of this character, we need a separator
        if (first.freq > 0) {
            if (heap->size == 0) break; // No separator available
            
            // Get second largest character as separator
            CharFreq second = pop(heap);
            result[resultLen++] = second.ch;
            second.freq--;
            
            // Put back the characters if they still have count > 0
            push(heap, first);
            if (second.freq > 0) {
                push(heap, second);
            }
        }
    }
    
    result[resultLen] = '\0';
    free(heap->data);
    free(heap);
    return result;
}

int main() {
    char s[100001];
    int repeatLimit;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &repeatLimit);
    
    char* result = solution(s, repeatLimit);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k log k)

O(n) to count frequencies, O(k log k) for heap operations where k ≤ 26 unique characters

⚡ Linearithmic

Space Complexity

O(k)

Heap stores at most k unique characters where k ≤ 26

✓ Linear Space

23.4K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Max Heap Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler