Leetcode Problem 730. Count Different Palindromic Subsequences

730. Count Different Palindromic Subsequences

Leetcode Solutions

Initialize a 2D array dp of size n x n to zero, where n is the length of the string s.
Precompute the next and prev arrays to find the next and previous occurrences of each character.
Iterate over all possible lengths of substrings from 1 to n.
For each substring length, iterate over all possible starting indices i.
For each starting index i, calculate the ending index j.
If s[i] equals s[j], find the range within i and j where the character does not change.
Update dp[i][j] based on the number of palindromic subsequences within the inner substring and the occurrences of the current character.
Add the count of single-character palindromes if they exist within the current substring.
Return the sum of palindromic subsequences starting with any character at the whole string length modulo 10^9 + 7.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen