Count Strings Without AAA or BBB

Problem

Count the strings of length n over the alphabet a and b that contain neither aaa nor bbb as a substring.

Track the last character and whether the current run has length 1 or 2. Adding the other character is always allowed, while continuing the run is only allowed from a run of length 1.

Hint

A run is never allowed to grow beyond two, so the state only needs a run flag.

Test cases

case 1

in: [1]

expected: 2

case 2

in: [2]

expected: 4

case 3

in: [3]

expected: 6

case 4

in: [4]

expected: 10

case 5

in: [5]

expected: 16

Starter codePython

def count_strings_without_aaa_bbb(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor