Issue

This Content is from Stack Overflow. Question asked by Melani Breana

Given a string s, which consists of characters "0" and "1" only, return the number of subsequences of length 5, which are palindromes.

As the number can be really big, return the answer mod(10^9 +7)

Test case 1:

input: "0100110"

output: 5

indices(1,2,3,6,7) -> "01010"

indices(1,2,3,5,7) -> "01010"

indices(1,2,4,6,7) -> "01010"

indices(1,2,4,5,7) -> "01010"

indices(1,2,5,6,7) -> "01110"

5 mod(10^9 +7) = 5

Test case 2:

input: "010110"

output: 3

indices(1,2,3,4,6) -> "01010"

indices(1,2,3,5,6) -> "01010"

indices(1,2,4,5,7) -> "01110"

indices(1,2,4,5,7) -> "01010"

indices(1,2,5,6,7) -> "01110"

5 mod(10^9 +7) = 5

Test case 3

input: "01111"

output: 0

There is no palindromic subsequence of length 5

I have been trying to solve the challenge above in python. I came up with a dynamic programming approach for counting palindromic subsequences which is quadratic O(n^2) where n is length of string, but I keep getting time limit exceeded. I think there is a more optimised solution that takes advantage of the characters being just "0" and "1" but I cant figure it out (I might be wrong).

Any input is highly appreciated, thanks.

Here is the code I tried

def countSubSequences(s):
    output = 0
    n = len(s)
    dp = [[0]*n]*n

    for i in range(n-2,-1,-1):
        for j in range(i+2,n):
            if dp[i+1][j] == dp[i+1][j-1]:
                dp[i][j] = dp[i][j-1] + 0
            else:
                dp[i][j] = dp[i][j-1] + (dp[i+1][j] - dp[i+1][j-1])
            
            if s[i] == s[j]:
                dp[i][j] += j-i-1

    for i in range(n):
        for j in range(i+4,n):
            if s[i] == s[j]:
                output += dp[i+1][j-1]

    return output % ((10**9) + 7)

Solution

Keeping track of counts of all subsequences up to five characters, takes about one second for a random string of length 100,000. Code including testing (Try it online!):

import random
from itertools import combinations
from math import comb
from time import time
from collections import Counter

mod = 10**9 + 7

def countSubSequences(s):
    ctr = Counter([''])
    fives = 0
    for c in s:
        for ss, cnt in list(ctr.items()):
            ss += c
            if len(ss) < 5:
                ctr[ss] += cnt
            elif ss == ss[::-1]:
                fives += cnt
    return fives % mod

for _ in range(10):
    s = ''.join(random.choices('01', k=30))
    expect = sum(c == c[::-1] for c in combinations(s, 5)) % mod
    result = countSubSequences(s)
    print(result == expect, expect, result)

n = 100000
print(comb(n, 5) % mod)
print(countSubSequences('0' * n))

t = time()
print(countSubSequences(''.join(random.choices('01', k=n))), time() - t)

Sample output:

True 33636 33636
True 27591 27591
True 34409 34409
True 31441 31441
True 35551 35551
True 29305 29305
True 34632 34632
True 34683 34683
True 54957 54957
True 33009 33009
502061291
502061291
595650700 1.2116138935089111

Optimized version that’s about 20 times faster, can even solve length 1,000,000 in less than a second (Try it online!). This combines equivalent subsequences, for example Oyxy keeps track of the number of all subsequences of length 4 which start with 0 and their second and fourth character are the same.

def countSubSequences(s):
    O = I = OO = OI = IO = II = OOx = OIx = IOx = IIx = Oyxy = Iyxy = zyxyz = 0
    for c in s:
        if c == '0':
            zyxyz += Oyxy
            Iyxy += IOx
            Oyxy += OOx
            IIx += II
            IOx += IO
            OIx += OI
            OOx += OO
            IO += I
            OO += O
            O += 1
        else:
            zyxyz += Iyxy
            Iyxy += IIx
            Oyxy += OIx
            IIx += II
            IOx += IO
            OIx += OI
            OOx += OO
            II += I
            OI += O
            I += 1
    return zyxyz % mod

Answered by Kelly Bundy
This Question and Answer are collected from stackoverflow and tested by JTuto community, is licensed under the terms of CC BY-SA 4.0.