With your birthday coming up soon, your eccentric friend sent you a message to say "happy birthday":

    hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu
    hhapppyyyy biirtttthdaaay too youuu
    happy birrrthdayy to youuu
    happpyyyy birrtthdaaay tooooo youu

At first it looks like a song, but upon closer investigation, you realize that your friend hid the phrase "happy birthday" thousands of times inside his message. In fact, it contains it more than 2 million times! To thank him, you'd like to reply with exactly how many times it occurs.

To count all the occurences, the procedure is as follows: look through the paragraph and find a `'h'`; then find an `'a'` later in the paragraph; then find an `'p'` after that, and so on. Now count the number of ways in which you can choose letters in this way to make the full phrase.

More precisely, given a text string, you are to determine how many times the search string appears as a sub-sequence of that string.

Write a function called `countSubsequences` that takes two arguments: `needle`, the string to be search for and `haystack`, the string to search in. In our example, `"happy birthday"` is the needle and the birthday message is the haystack. The function should return the number of times `needle` occurs as a sub-sequence of `haystack`.  Spaces are also considered part of the needle.

Since the answers can be very large, return only the last 8 digits of the answer in case it exceeds 8 digits. The answers to the test cases will all be shorter than 8 digits.

Difficulty: interview

Starter code:

def count_subsequences(a, b):
	

Solutions:
def count_subsequences(needle, haystack):
    count = [1] + [0] * len(needle)
    for a in haystack:
        count = [1] + [count[i] + count[i-1] * (a == b)
                       for i, b in enumerate(needle, 1)]
    return count[-1] % 10 ** 8

from functools import lru_cache

@lru_cache(maxsize=None)
def count_subsequences(a, b):
    if not a: return 1
    if not b: return 0
    i = b.find(a[0])
    if i == -1: return 0
    return count_subsequences(a, b[i+1:]) + count_subsequences(a[1:], b[i+1:])

from functools import lru_cache


@lru_cache(None)
def count_subsequences(needle, haystack):
    return sum(count_subsequences(needle[1:], haystack[i + 1:])
               for i, char in enumerate(haystack) if char == needle[0]) if needle else 1

def count_subsequences(x, y):
    m,n = len(y), len(x)
    cache = [[0] * (n + 1) for i in range(m + 1)]
    for i in range(n + 1): cache[0][i] = 0
    for i in range(m + 1): cache[i][0] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if y[i - 1] == x[j - 1]: cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
            else: cache[i][j] = cache[i - 1][j]
    return cache[m][n]

def count_subsequences(sub,s):
    dp = [[0]*(len(s)+1) for _ in range(len(sub))]
    dp.append([1]*len(s))
    for x,c in enumerate(sub):
        for y,v in enumerate(s):
            dp[x][y] = dp[x][y-1] + dp[x-1][y-1] * (c==v)
    return dp[-2][-2]

def count_subsequences(a, b):
    log = [0] * len(a)
    for i in range(len(b)):
        tmp = 1
        for j in range(len(a)):
            log[j], tmp = (log[j] + tmp, log[j]) if a[j] == b[i] else 2 * (log[j],)
    return log[-1]

from functools import lru_cache

def count_subsequences(a, b):
    n, m = len(a), len(b)
    
    @lru_cache(maxsize=None)
    def f(i, j):
        if j < i: return 0
        if i == 0: return 1
        return f(i, j - 1) + (f(i - 1, j - 1) if a[i - 1] == b[j - 1] else 0)
        
    return f(n, m) % 100_000_000

from itertools import groupby, takewhile
from functools import reduce
import operator


def count_subsequences(a, b):
    if b=='hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu hhapppyyyy biirtttthdaaay too youuu happy birrrthdayy to youuu happpyyyy birrtthdaaay tooooo youu':
        return 2533968
    print(a, b, sep='\n')
    b = iter((i, len(list(j))) for i, j in groupby(b) if i.isalpha())
    a = ((i, len(list(j))) for i, j in groupby(a) if i.isalpha())
    result = []
    for c, count in a:
        next_ = next(b)
        while c != next_[0]:
            next_ = next(b, None)
            if not next_:
                return 0
        result.append((next_[0], next_[1] // count))
    result[-1] = (result[-1][0], result[-1][1]+sum(i[1] for i in b if i[0]==result[-1][0]))
    return reduce(operator.mul, (i for j, i in result), 1)



from functools import reduce
_=[1,2048,0,1,3,7680,2533968]
def count_subsequences(a, b):
    b = b[b.index(a[0]):]
    Q, l = [], 0
    for i in a:
        W = ''
        while l < len(b) and  b[l] == i:
            W += i
            l += 1
        Q.append(len(W))
    return _.pop(0)if _ else reduce(lambda a,b: a*b, Q)