Construct String With Repeat Limit

Problem Description

So, you want to construct a string from a given set of characters, but there’s a catch! You can’t have any character repeating more than a specified limit. It’s like trying to eat your favorite dessert but your mom says, “One slice only!” and you’re left there, staring at the cake, contemplating life choices.

Imagine you have a box of colorful candies, but your friend (who clearly has too much power) says you can only take a certain number of each color. You want to make the most colorful candy necklace possible without breaking the rules. This is essentially what the problem is asking you to do, but with strings instead of candies.

Code Solution

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        ans = ''
        count = collections.Counter(s)

        while True:
            addOne = ans and self._shouldAddOne(ans, count)
            c = self._getLargestChar(ans, count)
            if c == ' ':
                break
            repeats = 1 if addOne else min(count[c], repeatLimit)
            ans += c * repeats
            count[c] -= repeats

        return ans

    def _shouldAddOne(self, ans: str, count: collections.Counter) -> bool:
        for c in reversed(string.ascii_lowercase):
            if count[c]:
                return ans[-1] == c
        return False

    def _getLargestChar(self, ans: str, count: collections.Counter) -> int:
        for c in reversed(string.ascii_lowercase):
            if count[c] and (not ans or ans[-1] != c):
                return c
        return ' '
    

Approach

The approach taken in this solution is quite clever. It uses a counter to keep track of how many times each character appears in the input string. The algorithm then constructs the result string by repeatedly adding the largest available character, while respecting the repeat limit. If the last character added is the same as the largest available character, it checks if it can add a different character to avoid exceeding the limit.

Time and Space Complexity

Time Complexity

O(n), where n is the length of the input string. The algorithm processes each character a limited number of times.

Space Complexity

O(1), since the space used for the counter is constant (limited to the number of lowercase letters).

Real-World Example

Think of it like organizing a party where you have a limited number of balloons of each color. You want to create the most vibrant display without having too many of the same color in one spot. This problem is all about balancing the colors (or characters) to create a visually appealing arrangement (or string) while adhering to the rules set by your friend (or the repeat limit).