6

Given a binary string S, find the number of palindromic subsequences of length 5. A palindromic subsequence of length 5 is a list of 5 increasing indices of the array a < b < c < d < e, such that the concatenation of S[a]S[b]S[c]S[d]S[e] forms a palindrome. Two palindromic subsequences are considered different if their list of indices are different.

My Thoughts:

I came up with a recursion as follows:

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?

7
  • 1
    "if there indexes are different even if they are same..": could you repeat ?
    – user1196549
    Commented Sep 6, 2022 at 9:39
  • "The indexes may not be contiguous.": this seems to be a key constraint, but I really can't figure out the meaning.
    – user1196549
    Commented Sep 6, 2022 at 9:41
  • 1
    Suggestion: "The palindrome subsequences are counted with multiplicity: two subsequences given by different sets of indices count as different even if the resulting palindromes are the same."
    – Stef
    Commented Sep 6, 2022 at 9:42
  • 2
    @YvesDaoust "aaa" has 3 different palindromic subsequences of length 2: indices (0, 1), and (0, 2), and (1, 2), even though the actual subsequences are all the same "aa". Indices (0, 2) is an example of noncontiguous indices, i.e., we are looking for subsequences, NOT substrings.
    – k_ssb
    Commented Sep 6, 2022 at 9:42
  • @YvesDaoust I think "The indexes may not be contiguous" is just emphasis on the fact that we're looking for all subsequences, not just substrings.
    – Stef
    Commented Sep 6, 2022 at 9:42

2 Answers 2

9

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

   
6
  • 1
    @k_ssb Yes, I interpreted "binary string" as sequence of 0 and 1
    – MBo
    Commented Sep 6, 2022 at 9:48
  • Unless I'm mistaken, complexity for this should be O(n), right? O(n) to get counts of 0 and 1 for any given index, O(n) for counts of 00, 01, ... using counts of 0, 1, then again O(n) for the palindrome counts.
    – tobias_k
    Commented Sep 6, 2022 at 10:02
  • @tobias_k Yes, complexity is linear, space complexity too. One left-to right scan, counting both 0/1 and pairs counts, storing pairs counts, then right-to left scan, and now we don't need to store pair counts, using them immediately
    – MBo
    Commented Sep 6, 2022 at 10:05
  • 3
    @nicku You're making me blush ;) I am not "guru", just want to "train my brain". Read any good basic Algorthms course book like Cormen, Sedgewick, Sciena etc. There are many interesting problems and brilliant answers in algorithms. Try to elaborate own solutions, then look at experienced users answers.
    – MBo
    Commented Sep 6, 2022 at 10:58
  • 1
    @nicku Along with MBo's answer I'd like to introduce competitive programming(CP). This problem is very similar to problems in CP contests. I'd suggest you to participate in contests, and solve lots of problems, you'd naturally get better at it. Good luck :)
    – sharpnife
    Commented Sep 6, 2022 at 11:40
1
  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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.