String overlaps

The total numbers of strings with length n and k colors that cannot overlap themselves are given by

a[0] = 1; a[n_] := k a[n - 1] - If[EvenQ[n], a[n/2], 0]

Up to reversal and interchange of A and B, the first few overlap-free strings with 2 colors are A, AB, AAB, AAAB, AABB.

The shortest pairs of strings of 2 elements with no self- or mutual overlaps are {"A", "B"}, {"AABB", "AABAB"}, {"AABB", "ABABB"}; there are a total of 13 such pairs with strings up to length 5, and 85 with strings up to length 6.

The shortest non-overlapping triple of strings is {"AAABB", "ABABB","ABAABB"} and its variants. There are a total of 36 such triples with no string having length more than 6.