String Without AAA or BBB - Practice Coding Problems

String Without AAA or BBB - Problem

String Greedy Medium

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
The substring 'bbb' does not occur in s

You need to construct a valid string that uses all the given characters while avoiding three consecutive identical characters.

Input & Output

Example 1 — Basic Case

$ Input: a = 1, b = 2

› Output: "bab"

💡 Note: We have 1 'a' and 2 'b's. Since b > a, we can start with 'b', then 'a', then 'b' to get "bab". No 'aaa' or 'bbb' patterns exist.

Example 2 — Equal Counts

$ Input: a = 2, b = 1

› Output: "aab"

💡 Note: We have 2 'a's and 1 'b'. Since a > b, we can place "aa" then "b" to get "aab". This uses all characters without forbidden patterns.

Example 3 — Large Difference

$ Input: a = 1, b = 4

› Output: "bbabb"

💡 Note: With 4 'b's and 1 'a', we need to carefully place 2 'b's, then 'a', then remaining 'b's to avoid 'bbb' pattern.

Constraints

0 ≤ a ≤ 100
0 ≤ b ≤ 100
1 ≤ a + b ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Given counts: a=1, b=2

Process

Build string avoiding 'aaa' and 'bbb'

Output

Valid string: "bab"

Key Takeaway

🎯 Key Insight: Always place the more abundant character first, but limit consecutive placements to at most 2

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is to always prioritize the more abundant character while ensuring no three consecutive identical characters. The greedy approach works optimally: choose the character with higher remaining count, but switch when we've placed 2 consecutive. Time: O(a+b), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Permutations	O((a+b)!)	O(a+b)	Generate all possible strings and check validity
Greedy Construction	O(a+b)	O(1)	Build string greedily, always choosing the more abundant character
Smart Greedy with Lookahead	O(a+b)	O(1)	Optimized greedy approach that places 2 characters when beneficial

Brute Force - Generate All Permutations — Algorithm Steps

Generate all permutations of a 'a's and b 'b's
For each permutation, check if it contains 'aaa' or 'bbb'
Return the first valid permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all permutations of characters

Check

Validate each permutation for 'aaa' or 'bbb'

Return

First valid permutation found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char* a, char* b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

int isValid(char* s, int len) {
    for (int i = 0; i <= len - 3; i++) {
        if ((s[i] == 'a' && s[i+1] == 'a' && s[i+2] == 'a') ||
            (s[i] == 'b' && s[i+1] == 'b' && s[i+2] == 'b')) {
            return 0;
        }
    }
    return 1;
}

int permute(char* str, int start, int len, char* result) {
    if (start == len) {
        if (isValid(str, len)) {
            strcpy(result, str);
            return 1;
        }
        return 0;
    }
    
    for (int i = start; i < len; i++) {
        swap(&str[start], &str[i]);
        if (permute(str, start + 1, len, result)) {
            return 1;
        }
        swap(&str[start], &str[i]);
    }
    return 0;
}

char* solution(int a, int b) {
    int total = a + b;
    char* chars = (char*)malloc((total + 1) * sizeof(char));
    char* result = (char*)malloc((total + 1) * sizeof(char));
    
    // Fill with 'a's and 'b's
    for (int i = 0; i < a; i++) chars[i] = 'a';
    for (int i = 0; i < b; i++) chars[a + i] = 'b';
    chars[total] = '\0';
    
    permute(chars, 0, total, result);
    free(chars);
    return result;
}

int main() {
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    char* result = solution(a, b);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((a+b)!)

Generating all permutations of a+b characters takes factorial time

✓ Linear Growth

Space Complexity

O(a+b)

Space for storing one permutation and recursion stack

✓ Linear Space

34.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler