2015 AIME II Problem 12

The condition says every run of identical letters has length at most $3.$ Classify valid strings by the length of their first run.

If $s_n$ counts valid length-$n$ strings starting with a given letter, then $s_n = s_{n-1} + s_{n-2} + s_{n-3}$

The condition says every maximal run of identical letters has length at most $3.$ Let $s_n$ count the valid strings of length $n$ whose first letter is A; by symmetry the answer is $2s_{10}.$ Removing the first run (of length $1,$ $2,$ or $3$) leaves a valid shorter string beginning with B, so $$s_n = s_{n-1} + s_{n-2} + s_{n-3}.$$

Starting from $s_1 = 1,$ $s_2 = 2,$ $s_3 = 4,$ the sequence runs $7, 13, 24, 44, 81, 149, 274,$ so $s_{10} = 274.$

The number of valid strings is $2 \cdot 274 = 548.$