Number of palindromes of length 5

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

   

1. Assume you have a function count(pattern, l,r) which returns the number of occurrences of the pattern in substring string[l:r].
2. For each index, consider it to be the center of the palindromic substring. There will be 2 elements to the left, and 2 elements to the right. Now, these 2 elements can only have 4 distinct values (from 0 to 3).
3. For an index i, the number of palindromic strings with i-th element at it's center would be sum(count(binary(x), 0,i) + count(binary(x).reverse, i, len(string))), where x is in range [0,3] and binary(x) returns the binary string representation of integer x.

This approach would take O(n * 4 * complexity of count function) time.

How to build the count function? With pre-processing/memoization, you can easily get the number of pattern occurences in O(1) time. Hint: there are only 4 patterns to track, each of which require only 2 counts. Simple counting and manipulation can get the job done.

There are only 8 palindromic strings of length 5. Generate all subsequences of length 5 and look them up in a stored table.

import itertools

palindromes= ("00000", "00100", "01010", "01110", "10001", "10101", "11011", "11111")

count= 0
for s in itertools.combinations("01100111", 5):
    if "".join(s) in palindromes:
        count+= 1
print(count)