长度为 5 的回文数

给定一个二进制字符串 S，找到长度为 5 的回文子序列的数量。长度为 5 的回文子序列是数组 a

我的想法：

我想出了如下的递归：

palin(s) = palin(s[1:]) +palin(s[:-1]) -palin(s[1:-1])

当 s[0] !=s[-1] 时，就是上面的情况。我们可以类似地处理其他情况。但这并不能只处理长度为 5 的回文。它将返回回文子序列的总数。我不确定这是否可以扩展以找到解决方案。有什么想法吗？

考虑下一个（线性复杂度）方法：

长度为 5 的回文由任何中心数字组成，并带有一对0..0, 0..1, 1..0, 1..1数字在左边，并且有对称对0..0, 1..0, 0..1, 1..1在左边。

因此，您可以从左到右遍历字符串，存储每个索引左侧每种可能对的数量，反方向执行相同操作。然后以索引为中心的回文数i is

P[i] = (Num of 00 left to i) * (Num of 00 right to i) + 
       (Num of 01 left to i) * (Num of 10 right to i) +    
       (Num of 10 left to i) * (Num of 01 right to i) + 
       (Num of 11 left to i) * (Num of 11 right to i) 

回文总数是P[i] over i=2..Len-2 range

如何获得 i 剩下的对数？只需计算 0 和 1，然后使用这些计数：

if S[i-1] == 0:
   (Num of 01 left to i) = (Num of 01 left to i-1) 
   (Num of 11 left to i) = (Num of 11 left to i-1) 
   (Num of 10 left to i) = (Num of 10 left to i-1) + (Count_1) 
   (Num of 00 left to i) = (Num of 00 left to i-1) + (Count_0)
   Count_0 += 1  
else:              #  1 forms new 0-1 pairs for all 0's at the left
                   #  and  new 1-1 pairs for all 1's at the left           
   (Num of 01 left to i) = (Num of 01 left to i-1) + (Count_0)
   (Num of 11 left to i) = (Num of 11 left to i-1) + (Count_1)
   (Num of 00 left to i) = (Num of 00 left to i-1)
   (Num of 10 left to i) = (Num of 10 left to i-1)
   Count_1 += 1 

要检查的 Python 代码（哑函数检查所有可能的组合以批准结果）

import itertools
def dumb(s):
    n = len(s)
    res = 0
    # produces all indices combinations
    for comb in itertools.combinations(range(n), 5):
        if s[comb[0]]==s[comb[4]] and s[comb[1]]==s[comb[3]]:
            res += 1
    return res

def countPal5(s):
    n = len(s)
    pairs = [[0, 0, 0, 0] for _ in range(n)]
    cnts = [0,0]
    for i in range(1, n-2):
        if s[i-1] == "0":
            if i >= 2:
                pairs[i-1][0]=pairs[i-2][0]+cnts[0]
                pairs[i-1][1]=pairs[i-2][1]
                pairs[i-1][2]=pairs[i-2][2]+cnts[1]
                pairs[i-1][3]=pairs[i-2][3]
            cnts[0] += 1
        else:
            if i >= 2:
                pairs[i-1][0]=pairs[i-2][0]
                pairs[i-1][1]=pairs[i-2][1]+cnts[0]
                pairs[i-1][2]=pairs[i-2][2]
                pairs[i-1][3]=pairs[i-2][3]+cnts[1]
            cnts[1] += 1
    #print(pairs)

    cnts = [0,0]
    res = 0
    for i in range(n-2, 1, -1):
        if s[i+1] == "0":
            if i < n-2:
                pairs[i+1][0]=pairs[i+2][0]+cnts[0]
                pairs[i+1][1]=pairs[i+2][1]
                pairs[i+1][2]=pairs[i+2][2]+cnts[1]
                pairs[i+1][3]=pairs[i+2][3]
            cnts[0] += 1
        else:
            if i < n-2:
                pairs[i+1][0]=pairs[i+2][0]
                pairs[i+1][1]=pairs[i+2][1]+cnts[0]
                pairs[i+1][2]=pairs[i+2][2]
                pairs[i+1][3]=pairs[i+2][3]+cnts[1]
            cnts[1] += 1
        res += pairs[i+1][0]*pairs[i-1][0] + pairs[i+1][1]*pairs[i-1][2] + pairs[i+1][2]*pairs[i-1][1] + pairs[i+1][3]*pairs[i-1][3]
    return res



    print(pairs)

print(countPal5("0110101001"))
print(dumb("0110101001"))

>>68
>>68