String Without AAA or BBB

medium greedy string

Problem

Given two integers a and b, return any string that contains exactly a letters 'a' and b letters 'b', and that does not contain either of the substrings "aaa" or "bbb".

Inputa = 4, b = 1

Output"aabaa"

Four 'a' and one 'b', and no run of three identical letters appears.

a (count of 'a')

b (count of 'b')

def str_without_3a3b(a, b):
    res = []
    while a > 0 or b > 0:
        tail = "".join(res[-2:])
        if tail == "aa":
            pick_a = False
        elif tail == "bb":
            pick_a = True
        else:
            pick_a = a >= b
        if pick_a:
            res.append("a"); a -= 1
        else:
            res.append("b"); b -= 1
    return "".join(res)

function strWithout3a3b(a, b) {
  const res = [];
  while (a > 0 || b > 0) {
    const tail = res.slice(-2).join("");
    let pickA;
    if (tail === "aa") pickA = false;
    else if (tail === "bb") pickA = true;
    else pickA = a >= b;
    if (pickA) { res.push("a"); a--; }
    else { res.push("b"); b--; }
  }
  return res.join("");
}

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder res = new StringBuilder();
        while (a > 0 || b > 0) {
            int n = res.length();
            boolean aa = n >= 2 && res.charAt(n - 1) == 'a' && res.charAt(n - 2) == 'a';
            boolean bb = n >= 2 && res.charAt(n - 1) == 'b' && res.charAt(n - 2) == 'b';
            boolean pickA = aa ? false : (bb ? true : a >= b);
            if (pickA) { res.append('a'); a--; }
            else { res.append('b'); b--; }
        }
        return res.toString();
    }
}

string strWithout3a3b(int a, int b) {
    string res;
    while (a > 0 || b > 0) {
        int n = (int)res.size();
        bool aa = n >= 2 && res[n - 1] == 'a' && res[n - 2] == 'a';
        bool bb = n >= 2 && res[n - 1] == 'b' && res[n - 2] == 'b';
        bool pickA = aa ? false : (bb ? true : a >= b);
        if (pickA) { res += 'a'; a--; }
        else { res += 'b'; b--; }
    }
    return res;
}

Explanation

We must build a string with exactly a letters 'a' and b letters 'b' that never has three of the same letter in a row. We build it one letter at a time using a simple greedy rule driven by the last two letters.

The rule: if the tail is already "aa", we are forced to write 'b' to avoid "aaa"; if the tail is "bb", we are forced to write 'a'. When there is no forced choice, we write whichever letter has more remaining (a >= b picks 'a').

Always spending down the more abundant letter keeps the two counts close, so we never get stuck holding too many of one letter at the end.

Example: a = 4, b = 1. We write a, a (now tail is "aa"), so forced b, then a, a → "aabaa", which has four 'a', one 'b', and no triple.

Each step either breaks a forming run or feeds the larger pile, so the final string always satisfies the counts and the no-three-in-a-row constraint.

Time: O(a + b) Space: O(a + b)