How hard is LeetCode 2484. Count Palindromic Subsequences?

LeetCode 2484. Count Palindromic Subsequences is rated Hard on LeetCode.

What is the time complexity of LeetCode 2484. Count Palindromic Subsequences?

The Python solution on this page runs in O(100 \times n).

What is the space complexity of LeetCode 2484. Count Palindromic Subsequences?

The Python solution on this page uses O(100 \times n) auxiliary space.

What topics does LeetCode 2484. Count Palindromic Subsequences cover?

LeetCode 2484. Count Palindromic Subsequences is tagged String and Dynamic Programming on LeetCode.

Count Palindromic Subsequences — LeetCode 2484 Python Solution

HardStringDynamic Programming

Problem: #2484
Pattern: Dynamic Programming
Reading time: 5 min
Source: leetcode.com

The problem

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 109 + 7.

Example

Input: s = "103301"
Output: 2
Explanation: There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301".

Python solution

Python

class Solution:
    def countPalindromes(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
        suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
        t = list(map(int, s))
        c = [0] * 10
        for i, v in enumerate(t, 1):
            for j in range(10):
                for k in range(10):
                    pre[i][j][k] = pre[i - 1][j][k]
            for j in range(10):
                pre[i][j][v] += c[j]
            c[v] += 1
        c = [0] * 10
        for i in range(n, 0, -1):
            v = t[i - 1]
            for j in range(10):
                for k in range(10):
                    suf[i][j][k] = suf[i + 1][j][k]
            for j in range(10):
                suf[i][j][v] += c[j]
            c[v] += 1
        ans = 0
        for i in range(1, n + 1):
            for j in range(10):
                for k in range(10):
                    ans += pre[i - 1][j][k] * suf[i + 1][j][k]
                    ans %= mod
        return ans

Complexity

Measure	Complexity
Time	O(100 \times n)
Space	O(100 \times n) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2484. Count Palindromic Subsequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2484. Count Palindromic Subsequences?: LeetCode 2484. Count Palindromic Subsequences is rated Hard on LeetCode.
What is the time complexity of LeetCode 2484. Count Palindromic Subsequences?: The Python solution on this page runs in O(100 \times n).
What is the space complexity of LeetCode 2484. Count Palindromic Subsequences?: The Python solution on this page uses O(100 \times n) auxiliary space.
What topics does LeetCode 2484. Count Palindromic Subsequences cover?: LeetCode 2484. Count Palindromic Subsequences is tagged String and Dynamic Programming on LeetCode.