如何查找所有不包含子串回文的字符串
How to find all strings that do not contain substring palindromes
免责声明：这是从 HackerRank 中提取的问题，但他们的编辑回答还不够，所以我希望得到更好的答案。如果它违反任何政策，请告诉我，我会把它记下来。
问题:
给你两个整数N和M，统计大小为M的字母表集合中长度为N的字符串的个数，其中不包含任何长度大于1的回文字符串作为连续子串。
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) 种方式来选择任何下一个符号（在前两个之后）- 基本上它不应该与前一个和 pred-previous 符号重合，它们不相等.
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 个选择。
免责声明：这是从 HackerRank 中提取的问题，但他们的编辑回答还不够，所以我希望得到更好的答案。如果它违反任何政策，请告诉我，我会把它记下来。
问题: 给你两个整数N和M，统计大小为M的字母表集合中长度为N的字符串的个数，其中不包含任何长度大于1的回文字符串作为连续子串。
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) 种方式来选择任何下一个符号（在前两个之后）- 基本上它不应该与前一个和 pred-previous 符号重合，它们不相等.
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 个选择。