计算回文的子串数

Question

我目前正试图解决一个在Hackerreank上出现的编程问题（链接到这里->；https://www.hackerrank.com/challenges/count-palindromes）。在

这个问题定义了一个由小写字符组成的字符串（a到z）

K是我输入的一个数字

我应该找到最小的字符串（上面的定义），它包含K个回文子字符串。（回文是一个序列，当倒转时会给出相同的序列）。在

好吧，这很有道理。现在，这是我的方法

假设我有一个字符串“aaaa”，它有10个回文子串的形式 a、 a，a，a aa，aa，aa aaa，aaa aaaa。 （因为不同索引中的字符被认为是唯一的。）

如果K取10，那么有10个回文子串的字符串的最小长度是4。因此答案是4（这个细节也可以在链接上找到）

现在我有了一个解决这个问题的方法，这并没有给我正确的结果。在

假设子串长度是N，如果它包含所有相同的字符，我将得到N的最小可能值

如果我假设是这样，那么：

大小1回文子串=N

大小2回文子串=N-1

大小3回文子串=N-2

。。在

。。在

。。在

大小N回文子串=1

使用此代码可以计算回文子字符串的数量

index = N
total = 0
while N > 0:
    total += N   
    N-=1

这段代码一步一步地计算从1到N的自然数之和

因此（N*N+1）/2是一个数可以拥有的回文子串的数目。因此对于一个特定的N，is（N*N+1）/2等于K，那么N就是答案。在

现在一个例子输入K是17

但N*N+1/2永远不会给出N（自然数）

谁知道我的方法有什么错误吗。感谢所有的帮助：）和抱歉的长问题

注：我真的不需要这个问题的解决方案，我只想找出我的算法出了什么问题

Answer 1

您的方法是错误的，因为您试图计算字符串中所有子字符串的数量。”假设子串长度是N，如果它包含所有相同的字符，我将得到N的最小可能值。这就是错误所在。由于分布N*（N+1）/2并没有覆盖整个自然数系，所以会有几个K值，它们可能会要求，而你却不能覆盖它。17就是这样的价值。在

aaaa -> it has 10 palindrome substrings.
aaaaa -> it has 15 palindrome substrings.
aaaaaa -> it has 21 palindrome substrings.

如您所见，回文子串的数量从N=5的15跳到N=6的21。因此，像只有17个回文子串这样的东西不可能用只有一个字符的字符串来表示。在

然而，如果你巧妙地添加另一个字母（或几个字母），你可以改变这种情况。E、 g

^{pr2}$

希望它能给你一些方向。我自己还没有找到答案，但我认为诀窍在于在一个字符的原始字符串中添加字母，因为上面的示例（顺便说一句）也使用了最小字符串。在

另一个例子：

aaaaabbc -> (minimum ?) string that has EXACTLY 19 palindrome substrings.

G00d幸运：）

Answer 2

求和的公式既不是（N*N+1）/2，也不是N*N+1/2。 正确的公式是（N*（N+1））/2。这总是一个自然数，因为N或（N+1）是偶数。因此，（N*（N+1））是偶数，（N*（N+1））/2是自然数。在