Give a binary string. I have to find the number of palindromic subsequences of length 5. The indexes may not be contiguous. And two palindromes are considered different if there indexes are different even if they are same..
.
My Thoughts:.
I came up with a recursion like.
palin(s)=
palin(s[1:]) palin(s[:-1]) -palin(s[1:-1])
The above will be the case when s[0] !=s[-1]. We can deal with other case similarly. But this doesn't take care of palindromes of length 5 only. It will return the total number of palindromic subsequences. I am not sure if this can be extended to find the solution.. any thoughts?
CodePudding user response：
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
CodePudding user response：
- Assume you have a function
count(pattern, l,r)which returns the number of occurrences of the pattern in substringstring[l:r]. - 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).
- For an index
i, the number of palindromic strings withi-thelement at it's center would besum(count(binary(x), 0,i) count(binary(x).reverse, i, len(string))), wherexis in range[0,3]andbinary(x)returns the binary string representation of integerx.
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.
CodePudding user response：
Note: Some other answers only consider palindromes of constant length 5, and only binary strings. My solution is more general, solving the problem for any length of palindromic subsequence for strings with any characters.
Suppose you've found the character 'A' at index 3 and 10. How many palindromic subsequences of length 5 start and end there? It's the exact same as the number of palindromic subsequences of length 3 within the input string between (exclusive) the two 'A' characters we found.
Now we have a recursive way of thinking about the problem: once we find two matching characters, we look for palindromic subsequences between those characters, with length 2 less.
This leads to the following algorithm in Python:
def num_palindromic_subsequences(string, length):
# Recursion base cases.
if length == 0:
return 1
if length == 1:
return len(string)
if length > len(string):
return 0
# Recursive case.
count = 0
for i in range(len(string)):
for j in range(i 1, len(string)):
if string[i] == string[j]:
count = num_palindromic_subsequences(string[i 1 : j], length - 2)
return count
This algorithm could be made more efficient with memoization or dynamic programming.
CodePudding user response：
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)