Think about the next (linear complexity) approach:
Length 5 palindrome is formed by any central digit, and with pair of 0..0, 0..1, 1..0, 1..1
digits at the left, and with symmetrical pair 0..0, 1..0, 0..1, 1..1
at the left.
So you can walk through the string from left to right, storing number of possible pairs of every kind left to each index, do the same in reverse direction. Then number of palindromes centered at index 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)
and overall number of palindromes is sum of P[i]
over i=2..Len-2
range
How to get number of pairs left to i? Just count 0's and 1's, and use these counts:
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 code to check (dumb function checks all possible combinations to approve result)
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