string - 如何查找所有不包含子串回文的字符串

Question

免责声明:这是从 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”。

感谢您帮助阐明这个问题。我真的希望有一个很好的答案来解决这个问题!

Answer 1

假设您一次构建一个字母的无回文字符串。对于第一个字母，您有 M 个选择，对于第二个，您有 M-1 个，因为您不能使用第一个字母。这是显而易见的。

对于前两个字母之后的每个字母，您不能使用前一个字母，也不能使用之前的字母，因此排除了两个选择。其他字母呢？好吧，如果使用其中一个创建一个回文，它必须是一个长度至少为 4 的回文 - 但是如果添加一个字母创建一个长度为 K+2 的回文，对于 K>=2，该字符串必须已经有一个长度为 K 的回文，用于构建新的回文。 (对于 K<2，这没问题。)由于字符串没有任何长度 >=2 的回文，我们可以得出结论，添加前两个字母以外的任何字母都可以。

因此，第一个字母有 M 个选择，第二个字母有 M-1 个选择，之后的每个字母有 M-2 个选择。