Construct String With Repeat Limit

Medium

Asked by:

4 views

Topics:

StringsGreedy Algorithms

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.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

1 <= repeatLimit <= s.length <= 10⁵
s consists of lowercase English letters.

Construct String With Repeat Limit

Medium

Asked by:

4 views

Topics:

StringsGreedy Algorithms

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.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

1 <= repeatLimit <= s.length <= 10⁵
s consists of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input string `s` and the value of `repeatLimit`?
Can the input string `s` be empty?
If the input string `s` contains characters other than lowercase English letters, how should I handle them? Should I throw an error or ignore them?
If it is impossible to construct a string that satisfies the given condition, what should I return? Should I return an empty string or null?
Is the provided `repeatLimit` always a positive integer?

Brute Force Solution

Approach

The brute force strategy for constructing a string with repeat limits means trying every possible combination of characters until we find one that works. We will build the string character by character, ensuring we never exceed the repeat limit for any character. This involves an exhaustive search to explore all viable arrangements.

Here's how the algorithm would work step-by-step:

Start with an empty string.
Consider each character we have available to us, one at a time.
Try adding that character to the end of our string.
Check if the number of times that character appears consecutively at the end of the string exceeds our repeat limit.
If it does exceed the limit, discard this option and try a different character.
If it does not exceed the limit, keep this option and consider the remaining characters to add to the string.
Repeat the process of adding characters and checking the repeat limit until our string is the desired length or we have used all available characters.
If, at any point, we cannot add any character without exceeding the repeat limit, backtrack to a previous step and try a different character there.
Keep track of all the valid strings we create this way.
From all valid strings, choose the one that uses all characters, or the longest string if it is impossible to use all characters.

Code Implementation

def construct_string_with_repeat_limit_brute_force(characters, repeat_limit):
    characters.sort(reverse=True)
    max_length = sum(frequency for char, frequency in characters)

    def backtrack(current_string, remaining_characters):
        if len(current_string) == max_length:
            return current_string

        best_string = ""

        for index in range(len(remaining_characters)):
            character, frequency = remaining_characters[index]

            # Check if we can add the current character without exceeding the repeat limit.
            if len(current_string) > 0 and current_string[-1] == character:
                last_char_count = 0
                for i in range(len(current_string) - 1, -1, -1):
                    if current_string[i] == character:
                        last_char_count += 1
                    else:
                        break
                if last_char_count == repeat_limit:
                    continue

            # If the character is available, try adding it.
            if frequency > 0:
                new_string = current_string + character
                new_remaining_characters = remaining_characters[:index] + \
                                            [(character, frequency - 1)] + \
                                            remaining_characters[index + 1:]
                new_remaining_characters.sort(reverse=True)

                # Recursively call backtrack to explore further possibilities.
                result = backtrack(new_string, new_remaining_characters)

                if len(result) == max_length:
                    return result

                if len(result) > len(best_string):
                    best_string = result

        return best_string

    # Initiate backtracking from an empty string.
    result = backtrack("", characters)
    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(k^n) – The brute force approach explores all possible combinations of characters. In the worst-case scenario, where we have k different characters to choose from and want to construct a string of length n, we potentially explore k options for each position. This leads to an exponential growth in the number of combinations we need to evaluate. Consequently, the time complexity is O(k^n), where k is the number of distinct characters and n is the desired length of the string. The repeat limit optimization can reduce the number of combinations, but in the worst case, it does not fundamentally change the exponential nature.

Space Complexity

O(N) – The brute force approach constructs strings character by character, potentially exploring many partial string combinations before finding a valid solution. In the worst-case scenario, the algorithm may need to store a significant number of intermediate string states for backtracking. The number of intermediate string states can grow proportionally to the length of the final string, which we denote as N, where N represents the length of the final constructed string. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To build the string efficiently, we'll focus on using the most frequent characters first, limiting repetition. We'll prioritize using the most available letters to construct the string in a greedy manner while respecting the repetition limit.

Here's how the algorithm would work step-by-step:

Count how many times each letter appears in the input string.
Sort the letters based on their frequency, with the most frequent letters coming first.
Start building the result string. Take the most frequent letter and add it to the result, but only up to the allowed repeat limit.
If we used up all occurrences of the most frequent letter, or reached the end of the input, move to the next most frequent letter.
If after adding letters up to the repeat limit, there are still more of this letter to add, we must insert a different letter to avoid exceeding the repeat limit. Look for the next most frequent letter that still has available occurrences.
If we find a different letter, add one instance of it. If not, then it means there is no letter available to break the streak so we can't construct the string. Return an empty string
Repeat the process of adding the most frequent letter up to the repeat limit, and then inserting another letter if necessary, until all letter occurrences are used up or we run into a situation where we cannot proceed due to the repeat limit.
The resulting string is the longest possible string you can construct respecting the repetition limit.

Code Implementation

def construct_string_with_repeat_limit(input_string, repeat_limit):
    letter_counts = {}
    for char in input_string:
        letter_counts[char] = letter_counts.get(char, 0) + 1

    sorted_letter_counts = sorted(letter_counts.items(), key=lambda item: item[1], reverse=True)

    result = ""

    while sorted_letter_counts:
        most_frequent_letter, most_frequent_count = sorted_letter_counts[0]
        
        # Add the most frequent letter up to the repeat limit or available count.
        add_count = min(most_frequent_count, repeat_limit)
        result += most_frequent_letter * add_count
        sorted_letter_counts[0] = (most_frequent_letter, most_frequent_count - add_count)

        if sorted_letter_counts[0][1] == 0:
            sorted_letter_counts.pop(0)
            continue

        # If more of the most frequent letter remains, find a different letter to insert.
        if sorted_letter_counts:
            second_most_frequent_letter, second_most_frequent_count = sorted_letter_counts[0]
            result += second_most_frequent_letter
            sorted_letter_counts[0] = (second_most_frequent_letter, second_most_frequent_count - 1)

            # Remove if count becomes zero.
            if sorted_letter_counts[0][1] == 0:
                sorted_letter_counts.pop(0)

            # Re-sort the list to maintain the order of frequency
            sorted_letter_counts = sorted(sorted_letter_counts, key=lambda item: item[1], reverse=True)

        else:
            # No other letters to break the streak, construction is impossible.
            return ""

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – Let n be the length of the input string. Initially, we count the frequency of each character, which takes O(n) time. We then sort the characters based on their frequencies. Sorting generally takes O(k log k) time, where k is the number of unique characters, but in this case k is limited to 26 (the English alphabet), making the sorting O(1). The main loop iterates through the sorted characters and appends them to the result string. In the worst case, we iterate over all characters to construct the string, which contributes a time complexity proportional to the length of the string. Inserting characters to avoid repeats requires searching for the next available character in the sorted structure, which can take up to O(k) time in each iteration of building the string. This adds O(n) to the initial O(n log n). Since the number of unique characters is constant, in the worst case, the complexity is dominated by the initial sort, which is dependent on the input string length and therefore is approximated as O(n log n).

Space Complexity

O(1) – The dominant space usage comes from counting character frequencies and sorting the characters by frequency. The character counts are stored, but since there are at most 26 distinct English letters, the space used for character counts and sorted letters is constant. The string construction itself doesn't use extra space that scales with the input string length N, aside from the result string (which is the output). Therefore, the auxiliary space used is constant, independent of the input string length N.

Edge Cases

Case	How to Handle
Empty input string s	Return an empty string since there are no characters to construct from.
repeatLimit is 0	Return an empty string, as no character can be repeated consecutively.
repeatLimit is 1	Return the string sorted in reverse lexicographical order as no character can appear more than once consecutively.
Input string contains only one unique character and its count is less than or equal to repeatLimit	Return the original string since it already satisfies the condition.
Input string contains only one unique character and its count is greater than repeatLimit	Return the character repeated repeatLimit times, as that's the maximum possible string.
All characters in the input string are the same.	Return the character repeated repeatLimit times, as any longer string will violate the repeat limit.
The lexicographically largest character has a count exceeding repeatLimit, and there are no other characters in the string.	Return the lexicographically largest character repeated repeatLimit times.
Input string with a skewed distribution where one or two characters are much more frequent than others.	Prioritize the largest character while respecting the repeat limit, switching to smaller characters to satisfy the condition and prevent over-repetition.