给定N个字符串,每个字符串的长度最多为1000。我们可以通过两个字符串的末尾连接它们。比如,如果一个字符串是“abc”,另一个字符串是“cba”,那么我们可以得到“abccba”和“cbaabc”。有些字符串可能没有与其他字符串连接在一起。同时,任何一个字符串都不能与自己连接。
我们只能将那些形成回文的两个字符串连接起来。因此,我需要告诉您在制作这样的配对之后剩下的最少字符串数量。
例子:假设我们有9个字符串:
aabbaabb
bbaabbaa
aa
bb
a
bbaa
bba
bab
ab
那么答案就是5。
解释:这里有5个字符串:
"aabbaabb" + "bbaabbaa" = "aabbaabbbbaabbaa"
"aa" + "a = "aaa"
"bba" + "bb" = "bbabb"
"bab" + "ab" = "babab"
"bbaa"
此外,总共可能会有1000个这样的字符串。