免责声明:这是从 HackerRank 提出的问题，但他们的编辑答案不够充分，所以我希望得到更好的答案。如果违反任何政策，请告诉我，我会将其删除。
问题: 给定两个整数 N 和 M。计算大小为 M 的字母集下不包含任何长度大于 1 的回文字符串作为连续子字符串的长度为 N 的字符串的数量。
N=2,M=2 -> 2::AA、AB、BA、BB
N=2,M=3 -> 6::AA、AB、AC、BA、BB、BC 、CA、CB、CC
ABCDE 计数，因为它不包含任何回文子字符串。
ABCCC 不算数，因为它包含“CCC”，即长度 >1 的回文。
社论 这是提供的答案，我认为这是错误的:
对于 N>=3，有 (M−2) 种方法来选择任何下一个符号(在前两个之后) - 基本上它不应该与前一个和前一个前一个符号重合，它们不相等。
If N=1, return M
If N=2, return M * (M-1)
If N>=3, return M * (M-1) * (M-2)^(N-2)
反例:N=4，M=3，“ABCC”
我的解决方案尝试 当我解决这个问题时，我试图找到所有包含回文子串的字符串，并从总数 M^N 中减去它。我在过度计数方面遇到了很多问题。例如，“ABABA”具有n=3的“ABA”、“BAB”、“ABA”，以及n=5的“ABABA”。
感谢您为阐明此问题提供的任何帮助。我真的希望有一个好的答案来解决这个问题!
最佳答案
假设您一次构建一个字母的无回文字符串。对于第一个字母，您有 M 个选择，对于第二个字母，您有 M-1，因为您不能使用第一个字母。这是显而易见的。
对于前两个字母之后的每个字母，您不能使用前一个字母，也不能使用之前的字母，因此消除了两个选择。那么其他字母呢？好吧，如果使用其中之一创建回文，则它必须是长度至少为 4 的回文 - 但如果添加一个字母创建长度为 K+2 的回文(对于 K>=2)，则该字符串必须已经有一个长度为 K 的回文，用于构建新的回文。 (对于 K<2，这是可以的。)由于字符串没有任何长度 >=2 的回文，我们可以得出结论，添加除前两个字母之外的任何字母都可以。
因此，第一个字母有 M 个选择，第二个字母有 M-1 个选择，之后的每个字母有 M-2 个选择。
关于string - 如何查找所有不包含子串回文的字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30381651/