Jobs

Interviews

Discussions

String Without AAA or BBB

Medium

Asked by:

40 views

Topics:

StringsGreedy Algorithms

Given two integers a and b, return any string s such that:

s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters,
The substring 'aaa' does not occur in s, and
The substring 'bbb' does not occur in s.

Example 1:

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: a = 4, b = 1
Output: "aabaa"

Constraints:

0 <= a, b <= 100
It is guaranteed such an s exists for the given a and b.

Try coding it in LeetCode

String Without AAA or BBB

Medium

Asked by:

40 views

Topics:

StringsGreedy Algorithms

Given two integers a and b, return any string s such that:

s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters,
The substring 'aaa' does not occur in s, and
The substring 'bbb' does not occur in s.

Example 1:

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: a = 4, b = 1
Output: "aabaa"

Constraints:

0 <= a, b <= 100
It is guaranteed such an s exists for the given a and b.

Try coding it in LeetCode

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 possible values for A and B? Are they only positive integers?
What happens if A and B are equal? Is there a preferred output string?
If no string can satisfy the condition, what should I return? Should I return an empty string, or throw an error?
Is there a maximum length for the resulting string? What are the constraints on the sum of A and B?
If multiple valid strings exist, is any valid string acceptable, or is there a specific preference (e.g., lexicographically smallest)?

Brute Force Solution

Approach

The brute force approach means trying every possible string arrangement. We'll keep building up strings by adding 'A's and 'B's, making sure that at no point do we accidentally create 'AAA' or 'BBB'.

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

Start with an empty string.
Consider adding an 'A' to the string. Check if the new string contains 'AAA'. If it does, discard it. Otherwise, keep it as a possible string.
Also, consider adding a 'B' to the original empty string. Check if the new string contains 'BBB'. If it does, discard it. Otherwise, keep it as a possible string.
Now, for each of the possible strings we have, again consider adding an 'A'. Check each new string for 'AAA'. Discard if it exists, otherwise keep it.
Do the same by adding a 'B' to each of our possible strings, checking for 'BBB' and discarding as necessary.
Keep doing this process, adding either 'A' or 'B' to all of our possible strings, and checking for the forbidden sequences. Do this until all of our strings reach the requested length.
From all of the possible strings of the correct length that we created, return any one of them. They are all valid.

Code Implementation

def generate_string_no_aaa_bbb_brute_force(a_count, b_count):
    possible_strings = [""]

    target_length = a_count + b_count

    while possible_strings:
        current_string = possible_strings.pop(0)

        if len(current_string) == target_length:
            return current_string

        # Attempt adding 'A' to current string
        potential_string_with_a = current_string + 'A'

        # Prevents 'AAA' sequences
        if 'AAA' not in potential_string_with_a:

            possible_strings.append(potential_string_with_a)

        # Attempt adding 'B' to current string
        potential_string_with_b = current_string + 'B'

        # Prevents 'BBB' sequences
        if 'BBB' not in potential_string_with_b:

            possible_strings.append(potential_string_with_b)

    return ""

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible string combinations of length n. At each step, we consider adding either 'A' or 'B', effectively doubling the number of candidate strings in the worst case. Since we do this for each of the n positions in the string, the number of possible strings grows exponentially. Checking each string for 'AAA' or 'BBB' takes O(1) time as the substring length is constant. Therefore, the total number of operations grows as 2 multiplied by itself n times, yielding a time complexity of O(2^n).

Space Complexity

O(2^N) – The algorithm maintains a collection of possible strings as it builds them. In the worst-case scenario, where very few strings are discarded because they contain 'AAA' or 'BBB', the number of possible strings roughly doubles with each character added. Therefore, to create a string of length N, the algorithm might potentially store 2^N possible intermediate strings. Thus, the space required grows exponentially with N, where N is the length of the desired string.

Optimal Solution

Approach

To avoid three 'A's or three 'B's in a row, we build the string carefully by prioritizing the character that appears more frequently. This ensures we use up the larger quantity while preventing long consecutive sequences of the same character. We intelligently switch between 'A' and 'B' based on their remaining counts.

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

Figure out how many 'A's and 'B's you have to begin with.
Keep track of how many 'A's and 'B's are left as you build the string.
If you have more of one character, add that character to the string first. This helps use up the more frequent character quicker.
However, before adding the more frequent character, make sure you haven't just added two of the same character in a row. If you have, you need to add the other character instead.
If you run out of one character, just keep adding the other one until you're done. It will never violate the rule if you already ran out of the other character.
Repeat these steps until you've used all your 'A's and 'B's.

Code Implementation

def string_without_aaa_or_bbb(number_of_a, number_of_b):
    result = ""
    a_character = 'a'
    b_character = 'b'

    # Determine which character is more frequent
    if number_of_b > number_of_a:
        number_of_a, number_of_b = number_of_b, number_of_a
        a_character, b_character = b_character, a_character

    while number_of_a > 0 or number_of_b > 0:
        # Add the more frequent character unless we just added two of them
        if len(result) >= 2 and result[-1] == a_character and result[-2] == a_character:
            if number_of_b > 0:
                result += b_character
                number_of_b -= 1
            else:
                result += a_character
                number_of_a -= 1

        else:
            if number_of_a > number_of_b:
            #Using more frequent character
                result += a_character
                number_of_a -= 1
            elif number_of_b > 0:
            #Use b because it is more frequent or equal
                result += b_character
                number_of_b -= 1
            else:
            #a is only option
                result += a_character
                number_of_a -= 1

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates until both A and B counts are exhausted. In each iteration, a constant number of operations are performed: comparing counts, checking the last two characters of the string, and appending a character. The number of iterations is directly proportional to the sum of the initial counts of A and B, which can be considered the input size, n. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm constructs a string of length N, where N is the sum of the initial counts of 'A' and 'B'. This string is the primary auxiliary space used. While we also use a few integer variables to keep track of the counts of A and B, their space usage is constant. Therefore, the dominant factor in space complexity is the size of the resulting string which scales linearly with N.

Edge Cases

Case	How to Handle
A or B is zero	Return an empty string or the string of the non-zero character repeated as many times as its corresponding value, as 'aaa' or 'bbb' won't occur.
A and B are both zero	Return an empty string since no characters can be generated.
A is significantly larger than B (or vice versa)	Prioritize adding more of the larger count character while interleaving smaller count characters to avoid 'aaa' or 'bbb'.
A and B are equal	Alternate between 'a' and 'b' until both counts are exhausted, resulting in 'ababab...'.
A and B differ by only one	Alternate between 'a' and 'b' with the larger count character going first, ending with one instance of the larger count character.
Integer overflow when calculating string length	Ensure the sum of A and B does not exceed maximum integer value or maximum allowed string length to prevent errors.
A or B are negative integers	Throw an error or return an appropriate error message, since the number of occurrences cannot be negative.
The string length is very large and may cause memory issues.	Employ techniques like using a StringBuilder with an initial capacity or streaming the output if generating extremely long strings.

A or B is zero

How to Handle:

Return an empty string or the string of the non-zero character repeated as many times as its corresponding value, as 'aaa' or 'bbb' won't occur.

A and B are both zero

How to Handle:

Return an empty string since no characters can be generated.

A is significantly larger than B (or vice versa)

How to Handle:

Prioritize adding more of the larger count character while interleaving smaller count characters to avoid 'aaa' or 'bbb'.

A and B are equal

How to Handle:

Alternate between 'a' and 'b' until both counts are exhausted, resulting in 'ababab...'.

A and B differ by only one

How to Handle:

Alternate between 'a' and 'b' with the larger count character going first, ending with one instance of the larger count character.

Integer overflow when calculating string length

How to Handle:

Ensure the sum of A and B does not exceed maximum integer value or maximum allowed string length to prevent errors.

A or B are negative integers

How to Handle:

Throw an error or return an appropriate error message, since the number of occurrences cannot be negative.

The string length is very large and may cause memory issues.

How to Handle:

Employ techniques like using a StringBuilder with an initial capacity or streaming the output if generating extremely long strings.

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 possible values for A and B? Are they only positive integers?
What happens if A and B are equal? Is there a preferred output string?
If no string can satisfy the condition, what should I return? Should I return an empty string, or throw an error?
Is there a maximum length for the resulting string? What are the constraints on the sum of A and B?
If multiple valid strings exist, is any valid string acceptable, or is there a specific preference (e.g., lexicographically smallest)?

Brute Force Solution

Approach

The brute force approach means trying every possible string arrangement. We'll keep building up strings by adding 'A's and 'B's, making sure that at no point do we accidentally create 'AAA' or 'BBB'.

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

Start with an empty string.
Consider adding an 'A' to the string. Check if the new string contains 'AAA'. If it does, discard it. Otherwise, keep it as a possible string.
Also, consider adding a 'B' to the original empty string. Check if the new string contains 'BBB'. If it does, discard it. Otherwise, keep it as a possible string.
Now, for each of the possible strings we have, again consider adding an 'A'. Check each new string for 'AAA'. Discard if it exists, otherwise keep it.
Do the same by adding a 'B' to each of our possible strings, checking for 'BBB' and discarding as necessary.
Keep doing this process, adding either 'A' or 'B' to all of our possible strings, and checking for the forbidden sequences. Do this until all of our strings reach the requested length.
From all of the possible strings of the correct length that we created, return any one of them. They are all valid.

Code Implementation

def generate_string_no_aaa_bbb_brute_force(a_count, b_count):
    possible_strings = [""]

    target_length = a_count + b_count

    while possible_strings:
        current_string = possible_strings.pop(0)

        if len(current_string) == target_length:
            return current_string

        # Attempt adding 'A' to current string
        potential_string_with_a = current_string + 'A'

        # Prevents 'AAA' sequences
        if 'AAA' not in potential_string_with_a:

            possible_strings.append(potential_string_with_a)

        # Attempt adding 'B' to current string
        potential_string_with_b = current_string + 'B'

        # Prevents 'BBB' sequences
        if 'BBB' not in potential_string_with_b:

            possible_strings.append(potential_string_with_b)

    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Figure out how many 'A's and 'B's you have to begin with.
Keep track of how many 'A's and 'B's are left as you build the string.
If you have more of one character, add that character to the string first. This helps use up the more frequent character quicker.
However, before adding the more frequent character, make sure you haven't just added two of the same character in a row. If you have, you need to add the other character instead.
If you run out of one character, just keep adding the other one until you're done. It will never violate the rule if you already ran out of the other character.
Repeat these steps until you've used all your 'A's and 'B's.

Code Implementation

def string_without_aaa_or_bbb(number_of_a, number_of_b):
    result = ""
    a_character = 'a'
    b_character = 'b'

    # Determine which character is more frequent
    if number_of_b > number_of_a:
        number_of_a, number_of_b = number_of_b, number_of_a
        a_character, b_character = b_character, a_character

    while number_of_a > 0 or number_of_b > 0:
        # Add the more frequent character unless we just added two of them
        if len(result) >= 2 and result[-1] == a_character and result[-2] == a_character:
            if number_of_b > 0:
                result += b_character
                number_of_b -= 1
            else:
                result += a_character
                number_of_a -= 1

        else:
            if number_of_a > number_of_b:
            #Using more frequent character
                result += a_character
                number_of_a -= 1
            elif number_of_b > 0:
            #Use b because it is more frequent or equal
                result += b_character
                number_of_b -= 1
            else:
            #a is only option
                result += a_character
                number_of_a -= 1

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
A or B is zero	Return an empty string or the string of the non-zero character repeated as many times as its corresponding value, as 'aaa' or 'bbb' won't occur.
A and B are both zero	Return an empty string since no characters can be generated.
A is significantly larger than B (or vice versa)	Prioritize adding more of the larger count character while interleaving smaller count characters to avoid 'aaa' or 'bbb'.
A and B are equal	Alternate between 'a' and 'b' until both counts are exhausted, resulting in 'ababab...'.
A and B differ by only one	Alternate between 'a' and 'b' with the larger count character going first, ending with one instance of the larger count character.
Integer overflow when calculating string length	Ensure the sum of A and B does not exceed maximum integer value or maximum allowed string length to prevent errors.
A or B are negative integers	Throw an error or return an appropriate error message, since the number of occurrences cannot be negative.
The string length is very large and may cause memory issues.	Employ techniques like using a StringBuilder with an initial capacity or streaming the output if generating extremely long strings.

A or B is zero

How to Handle:

Return an empty string or the string of the non-zero character repeated as many times as its corresponding value, as 'aaa' or 'bbb' won't occur.

A and B are both zero

How to Handle:

Return an empty string since no characters can be generated.

A is significantly larger than B (or vice versa)

How to Handle:

Prioritize adding more of the larger count character while interleaving smaller count characters to avoid 'aaa' or 'bbb'.

A and B are equal

How to Handle:

Alternate between 'a' and 'b' until both counts are exhausted, resulting in 'ababab...'.

A and B differ by only one

How to Handle:

Alternate between 'a' and 'b' with the larger count character going first, ending with one instance of the larger count character.

Integer overflow when calculating string length

How to Handle:

Ensure the sum of A and B does not exceed maximum integer value or maximum allowed string length to prevent errors.

A or B are negative integers

How to Handle:

Throw an error or return an appropriate error message, since the number of occurrences cannot be negative.

The string length is very large and may cause memory issues.

How to Handle:

Employ techniques like using a StringBuilder with an initial capacity or streaming the output if generating extremely long strings.