Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome

Question

Given length L find the shortest string >= L formed only of as & bs such that adding some character (Either a or b) doesn't produce a new palindrome substring (never seen before palindrome)

For example for L = 1 there is the string aabbaba, adding "a" to it to result in aabbabaa will only produce the palindromes "a" and "aa" which were seen before at the 1st and 2nd character positions, but for example the string aabab doesn't work because adding "b" or "a" will produce the new palindromes "bb" and "ababa" respectively

I'm not even sure aabbaba is the optimal solution for L = 1. Any ideas on an algorithm to solve this fast?

Answer 1

Here are my results so far:

• L=1-7: "aabbaba" -> "aabbabaa" (or the mirror, confirming your result)
• L=8: "aaabbaba" -> "aaabbabaa" (or the mirror)
• L=9: "aaaabbbaba" -> "aaaabbbabaa" (or the mirror)

All futher L can be solved just by prefixing an additional a to the starting string.