We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String Without AAA or BBB

Number: 1026

Difficulty: Medium

Paid? No

Companies: Zalando

Problem Description

Given two integers a and b, generate any string s of length a + b that contains exactly a occurrences of the letter 'a' and exactly b occurrences of the letter 'b'. The string s must not contain the substring "aaa" or "bbb".

Key Insights

  • Use a greedy strategy to decide whether to append 'a' or 'b' at each step.
  • Monitor the last two characters in the constructed string to avoid forming three consecutive identical letters.
  • At any step, if one type of letter is much more frequent than the other, append two of that letter if it is safe to do so.
  • Once one letter count is zero, append the remaining letters from the other count, ensuring the constraint is not violated.

Space and Time Complexity

Time Complexity: O(a + b) – we build the string in one pass. Space Complexity: O(a + b) – the output string stores all characters.

Solution

We use a greedy approach to build the string one letter at a time. At each iteration, we decide whether to append 'a' or 'b' based on the remaining counts and the last two appended characters. If appending a particular letter would make three consecutive occurrences, we switch to the other letter. If one letter has a significantly higher count, we consider appending it twice when safe, to help balance the counts. The algorithm continues until all a and b letters are used.

Code Solutions

# Python solution
def strWithout3a3b(a, b):
    # Initialize the result string as a list for efficiency
    result = []
    
    # Loop until there are no more letters to use
    while a > 0 or b > 0:
        # Check for the case when the last two characters are the same letter.
        if len(result) >= 2 and result[-1] == result[-2]:
            # If the last two are 'a', we must append 'b'
            if result[-1] == 'a':
                result.append('b')
                b -= 1
            else:
                result.append('a')
                a -= 1
        else:
            # If no constraint from last two letters, append the letter with more remaining count.
            if a > b:
                result.append('a')
                a -= 1
            else:
                result.append('b')
                b -= 1
    # Join the list into a string and return it
    return ''.join(result)

# Example usage
print(strWithout3a3b(1, 2))  # Expected valid outputs: "abb", "bab", or "bba"
← Back to All Questions