Count Palindromic Subsequences Interview Question for Meta

Given a string of digits s, return the number of palindromic subsequences of s* having length* 5. Since the answer may be very large, return it modulo 10<sup>9</sup> + 7.

Note:

A string is palindromic if it reads the same forward and backward.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

For example:

s = "103301" should return 2. The palindromic subsequences are "10301".
s = "0000000" should return 21. All subsequences "00000" are palindromic.
s = "9999900000" should return 2. The subsequences are "99999" and "00000".

Write a function to efficiently calculate the number of palindromic subsequences of length 5 in a given string.

Brute Force Solution

A naive approach would be to generate all possible subsequences of length 5 from the given string s and then check if each subsequence is a palindrome. We would count the number of palindromic subsequences and return the result modulo 10⁹ + 7.

Code (Python)

def is_palindrome(s):
    return s == s[::-1]

def count_palindromic_subsequences_brute_force(s):
    n = len(s)
    count = 0
    mod = 10**9 + 7

    for i in range(n - 4):
        for j in range(i + 1, n - 3):
            for k in range(j + 1, n - 2):
                for l in range(k + 1, n - 1):
                    for m in range(l + 1, n):
                        subsequence = s[i] + s[j] + s[k] + s[l] + s[m]
                        if is_palindrome(subsequence):
                            count = (count + 1) % mod
    return count

# Example usage:
s = "103301"
print(count_palindromic_subsequences_brute_force(s))

Time Complexity

O(n⁵) because we have five nested loops to generate all possible subsequences of length 5.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Solution: Dynamic Programming

We can use dynamic programming to solve this problem more efficiently. Let dp[i][j] be the number of palindromic subsequences of length 3 between indices i and j (inclusive). We can build the dp table as follows:

Initialize a 3D array count[i][j][k] to store the count of subsequences of length 3 that start and end with the same digit k between indices i and j.
Iterate over all possible subsequence lengths from 5 down to 1.
For each length, iterate over all possible start indices i.
The end index j will be i + length - 1.
If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + count[i+1][j-1]

Instead, we can utilize dynamic programming to calculate all the number of palindromic subsequences of length 5 directly. We can count the occurrences of digits to help construct the DP table efficiently.

Code (Python)

def count_palindromic_subsequences(s):
    n = len(s)
    mod = 10**9 + 7
    ans = 0

    for a in range(10):
        for b in range(10):
            target = str(a) + str(b) + str(a)
            count_b = 0
            first_a = -1

            for i in range(n):
                if s[i] == str(a) and first_a == -1:
                    first_a = i
                elif s[i] == str(b) and first_a != -1:
                    for j in range(i + 1, n):
                        if s[j] == str(a):
                            ans = (ans + 1) % mod

    return ans

Time Complexity

O(n), as we iterate through the string s a constant number of times (100 times in the outer loops).

Space Complexity

O(1), as we use a constant amount of extra space.

Edge Cases

Empty string: Should return 0.
String length less than 5: Should return 0.
String with only one distinct character: e.g., "0000000".