How do you build the longest string from AA, BB and AB without three in a row?

Reported. A May 2023 "Berlin / online" post gave this statement and one example. There is no exact LeetCode equivalent; problems such as 984, String Without AAA or BBB and 1405, Longest Happy String are only cousins, because here the tokens are the blocks AA, BB and AB, not single letters.

Problem. You are given counts of the blocks AA, BB and AB. Build a longest string by concatenating those blocks so that the result does not contain AAA or BBB as a substring. The reported example: AA = 2, BB = 1, AB = 1 → ABAABBAA.

Inferred: any longest concatenation is acceptable if several exist; unused leftover blocks are allowed; counts are non-negative. Constraints were not published.

Approach. Each block has length 2, so maximising length is the same as using as many blocks as possible. Valid transitions, from the last two characters, are:

• after AA (ends in A): only BB
• after BB (ends in B): AA or AB
• after AB (ends in B): AA or AB

Two facts follow. First, every AB can be used: a run of ABs is always safe (ABABAB…), and that run can be placed at the start when you have at least as many AA as BB, or just after a leading BB otherwise. Second, AA and BB must alternate, so you can use all of the scarcer one and at most one extra of the other (|used_AA - used_BB| ≤ 1 when both are used).

Construction:

• if aa >= bb: (AB)* + (AA BB)* + (AA if aa > bb)
• if aa < bb: BB + (AB)* + (AA BB)* (this uses aa + 1 copies of BB)

Time and extra space are linear in the length of the answer.

public class BlocksWithoutTriple {
    static String buildFromBlocks(int aa, int bb, int ab) {
        String abs = "AB".repeat(ab);
        if (aa >= bb) return abs + "AABB".repeat(bb) + (aa > bb ? "AA" : "");
        return "BB" + abs + "AABB".repeat(aa);
    }

    public static void main(String[] args) {
        System.out.println(buildFromBlocks(2, 1, 1)); // ABAABBAA
        System.out.println(buildFromBlocks(0, 0, 3)); // ABABAB
        System.out.println(buildFromBlocks(2, 0, 0)); // AA  (the second AA would make AAAA)
        System.out.println(buildFromBlocks(0, 2, 0)); // BB
    }
}

Verified with OpenJDK 21.0.13: the first call prints ABAABBAA. The same construction was checked against a complete search for every triple of counts in 0..4; it always used the maximum number of blocks and never wrote AAA or BBB.

Edge cases. All counts zero; only AA or only BB (you can use at most one block); only AB (use them all); a large imbalance of AA and BB.