python - 计算回文子串的数量

Question

我目前正在尝试解决 Hackerreank 上的一个编程问题(链接在这里 -> https://www.hackerrank.com/challenges/count-palindromes)。

问题将字符串定义为由小写字符(a 到 z)组成

K 是我作为输入提供的数字

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

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

假设我有一个字符串“aaaa”，它有 10 个回文子串，形式如下一个，一个，一个，一个啊啊啊啊啊啊啊啊啊啊 (因为不同索引处的字符被认为是唯一的。)

所以如果 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，是(N * N+1)/2等于K，那么N就是答案。

现在一个样例输入K为17

但是 N * N+1/2 永远不会给出 N(自然数)

谁能告诉我我的方法有什么错误。感谢所有帮助 :) 很抱歉这个问题很长

P.S:我真的不需要问题的解决方案，我只是想弄清楚我的算法有什么问题

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 个。因此，像 HAVING EXACTLY 17 个回文子串这样的东西不可能由只有一个字符的字符串表示。

但是，如果你巧妙地适当加入另一个字母(或几个字母)，就可以改变这种情况。例如

aaaaabb -> it has 18 palindrome substrings. ( Added b,b,bb)

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

另一个例子:

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

G00d 运气 :)