string - 给定长度 L 找到仅由 as & bs >= L 组成的最短字符串，这样添加一些字符(a 或 b)不会产生新的回文

Question

给定长度 L 找到最短的字符串 >= L 仅由 as & bs 组成，这样添加一些字符(a 或 b)不会产生新的回文子串(在回文之前从未见过)

例如 L = 1有字符串aabbaba，在它上面加上“a”得到aabbaa，只会产生之前在第一个和第二个字符位置出现的回文“a”和“aa”，但例如字符串 aabab 不起作用，因为添加“b”或“a”将分别产生新的回文“bb”和“ababa”

我什至不确定 aabbaba 是 L = 1 的最优解。关于快速解决这个问题的算法有什么想法吗？

Answer 1

到目前为止，这是我的结果:

• L=1-7:“aabbaba”->“aabbabaa”(或镜像，确认您的结果)
• L=8:“aaabbaba”->“aaabbabaa”(或镜像)
• L=9:“aaaabbbaba”->“aaaabbbabaa”(或镜像)

所有进一步的 L 都可以通过在起始字符串前添加一个额外的 a 来解决。