String Without AAA or BBB

LeetCode 1026 | Difficulty: Medium

Medium

Problem Description

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`.

Topics: String, Greedy

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 48 ms)

Metric	Value
Runtime	48 ms
Memory	37.2 MB
Date	2022-02-01

Solution

public class Solution {
    public string StrWithout3a3b(int a, int b) {
     int count1 = 0, count2 = 0;
    int size = a + b;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < size; i++)
    {
        if (count1 == 2)
        {
            if (b > 0)
            {
                sb.Append("b");
                count1 = 0;
                count2++;
                b--;
            }
        }
        else if (count2 == 2)
        {
            if (a > 0)
            {
                sb.Append("a");
                count2 = 0;
                count1++;
                a--;
            }
        }
        else if (a > b)
        {
            sb.Append("a");
            a--;
            count1++;
        }
        else
        {
            sb.Append("b");
            b--;
            count2++;
        }
    }
    return sb.ToString();
}
}

📜 3 more C# submission(s)

Submission (2022-02-01) — 96 ms, 35.6 MB

public class Solution {
    public string StrWithout3a3b(int a, int b) {
     if(b>a) return StringWithoutHelper(b, a, "b", "a");
    return StringWithoutHelper(a, b, "a", "b");
    
}

private string StringWithoutHelper(int first, int second, string firstChar, string secondChar)
{
    int count1 = 0, count2 = 0;
    int size = first + second;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < size; i++)
    {
        if (count1 == 2 && second > 0)
        {
            sb.Append(secondChar);
            count1 = 0;
            count2++;
            second--;
        }
        else if (count2 == 2 && first > 0)
        {
            sb.Append(firstChar);
            count2 = 0;
            count1++;
            first--;
        }
        else if(first>second)
        {
            sb.Append(firstChar);
            first--;
            count1++;
        }
        else
        {
            sb.Append(secondChar);
            second--;
            count2++;
        }
    }
    return sb.ToString();
}
}

Submission (2022-02-01) — 106 ms, 35.1 MB

public class Solution {
    public string StrWithout3a3b(int a, int b) {
     int count1 = 0, count2 = 0;
    int size = a + b;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < size; i++)
    {
        if (count1 == 2 && b > 0)
        {
            sb.Append("b");
            count1 = 0;
            count2++;
            b--;
        }
        else if (count2 == 2 && a > 0)
        {
            sb.Append("a");
            count2 = 0;
            count1++;
            a--;
        }
        else if (a > 0 && a >= b && count1 < 2)
        {
            sb.Append("a");
            a--;
            count1++;
        }
        else if (b>0 && b >= a && count2 < 2)
        {
            sb.Append("b");
            b--;
            count2++;
        }
    }
    return sb.ToString();
}
}

Submission (2022-02-01) — 116 ms, 35.4 MB

public class Solution {
    public string StrWithout3a3b(int a, int b) {
     int count1 = 0, count2 = 0;
    int size = a + b;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < size; i++)
    {
        if (count1 == 2)
        {
            if (b > 0)
            {
                sb.Append("b");
                count1 = 0;
                count2++;
                b--;
            }
        }
        else if (count2 == 2)
        {
            if (a > 0)
            {
                sb.Append("a");
                count2 = 0;
                count1++;
                a--;
            }
        }
        else if (a >= b)
        {
            sb.Append("a");
            a--;
            count1++;
        }
        else if (b >= a)
        {
            sb.Append("b");
            b--;
            count2++;
        }
    }
    return sb.ToString();
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.