Problem of The Day: Construct String With Repeat Limit

7 min read 1445 words

Problem Statement

leetcode problem link

• Notes: need to review.

Editorial

Approach 1: Greedy Character Frequency Distribution

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord("a")] += 1

        result = []
        current_char_index = 25  # Start from the largest character
        while current_char_index >= 0:
            if freq[current_char_index] == 0:
                current_char_index -= 1
                continue

            use = min(freq[current_char_index], repeatLimit)
            result.append(chr(current_char_index + ord("a")) * use)
            freq[current_char_index] -= use

            if freq[current_char_index] > 0:  # Need to add a smaller character
                smaller_char_index = current_char_index - 1
                while smaller_char_index >= 0 and freq[smaller_char_index] == 0:
                    smaller_char_index -= 1
                if smaller_char_index < 0:
                    break
                result.append(chr(smaller_char_index + ord("a")))
                freq[smaller_char_index] -= 1

        return "".join(result)

using System;
using System.Text;

public class Solution {
    public string RepeatLimitedString(string s, int repeatLimit) {
        int[] freq = new int[26];
        foreach (char c in s) {
            freq[c - 'a']++;
        }

        StringBuilder result = new StringBuilder();
        int currentCharIndex = 25; // Start from the largest character

        while (currentCharIndex >= 0) {
            if (freq[currentCharIndex] == 0) {
                currentCharIndex--;
                continue;
            }

            int use = Math.Min(freq[currentCharIndex], repeatLimit);
            result.Append((char)(currentCharIndex + 'a'), use);
            freq[currentCharIndex] -= use;

            if (freq[currentCharIndex] > 0) { // Need to add a smaller character
                int smallerCharIndex = currentCharIndex - 1;
                while (smallerCharIndex >= 0 && freq[smallerCharIndex] == 0) {
                    smallerCharIndex--;
                }
                
                if (smallerCharIndex < 0) {
                    break;
                }
                
                result.Append((char)(smallerCharIndex + 'a'));
                freq[smallerCharIndex]--;
            }
        }

        return result.ToString();
    }
}

Explanation

• Greedy Strategy: To build the lexicographically largest string, always prioritize the largest available characters ('z' down to 'a').
• Frequency Array: Use a 26-slot array for counts. This is more efficient than a heap for small, fixed-size alphabets.
• Repeat Limit Handling:
  1. Append the largest available character up to the repeatLimit.
  2. If count remains, use exactly one next-best character (a “breaker”) to reset the streak.
  3. Why only one breaker? To return to the largest possible character as quickly as possible.

• Termination: Stop when no more “breaker” characters are available but the primary character still needs to be reset.

• Time Complexity: O(N * K), where N is string length and K=26. Each character addition may involve a small scan for the next best character.
• Space Complexity: O(K) for the frequency array.

Approach 2: Heap-Optimized Greedy Character Frequency Distribution

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        max_heap = [(-ord(c), cnt) for c, cnt in Counter(s).items()]
        heapify(max_heap)
        result = []

        while max_heap:
            char_neg, count = heappop(max_heap)
            char = chr(-char_neg)
            use = min(count, repeatLimit)
            result.append(char * use)

            if count > use and max_heap:
                next_char_neg, next_count = heappop(max_heap)
                result.append(chr(-next_char_neg))
                if next_count > 1:
                    heappush(max_heap, (next_char_neg, next_count - 1))
                heappush(max_heap, (char_neg, count - use))

        return "".join(result)

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    public string RepeatLimitedString(string s, int repeatLimit) {
        Dictionary<char, int> counts = new Dictionary<char, int>();
        foreach (char c in s) {
            if (!counts.ContainsKey(c)) counts[c] = 0;
            counts[c]++;
        }

        PriorityQueue<(char, int), char> maxHeap = new PriorityQueue<(char, int), char>(Comparer<char>.Create((a, b) => b.CompareTo(a)));
        foreach (var kvp in counts) {
            maxHeap.Enqueue((kvp.Key, kvp.Value), kvp.Key);
        }

        StringBuilder result = new StringBuilder();

        while (maxHeap.Count > 0) {
            (char character, int count) = maxHeap.Dequeue();
            int use = Math.Min(count, repeatLimit);
            result.Append(character, use);

            if (count > use && maxHeap.Count > 0) {
                (char nextChar, int nextCount) = maxHeap.Dequeue();
                result.Append(nextChar);
                if (nextCount > 1) {
                    maxHeap.Enqueue((nextChar, nextCount - 1), nextChar);
                }
                maxHeap.Enqueue((character, count - use), character);
            }
        }

        return result.ToString();
    }
}

Explanation

• Priority Queue: Use a max-heap to keep track of characters and their frequencies, ordered by character lexicographical value.
• Greedy Selection: Always pop the largest character from the heap to ensure the lexicographically largest result.
• Repeat Limit: Append the character up to repeatLimit times.
• Breaker Character: If more of the current character remains but the limit is reached, pop the next largest character as a single “breaker” to reset the streak, then push both back into the heap.

• Efficiency: Similar to the frequency array approach, but more flexible for larger alphabets.

• Time Complexity: O(N log K), where N is string length and K is the number of unique characters.
• Space Complexity: O(K) for the heap and frequency storage.