Leetcode Problem 2484. Count Palindromic Subsequences

2484. Count Palindromic Subsequences

Leetcode Solutions

Counting Prefixes and Suffixes

  1. Initialize a 3D array pre to store the count of two-character prefixes (XY) before each index.
  2. Initialize a 3D array suf to store the count of two-character suffixes (YX) after each index.
  3. Initialize a 1D array cnts to store the count of each digit in the string.
  4. Iterate through the string to fill the pre array with the count of prefixes before each index.
  5. Iterate through the string in reverse to fill the suf array with the count of suffixes after each index.
  6. Iterate through the string from the third character to the third-to-last character.
  7. For each character, iterate over all possible two-character combinations (0-9 for both characters).
  8. Multiply the counts from pre and suf arrays for each combination and add to the result.
  9. Return the result modulo 10^9 + 7.
UML Thumbnail

Simple L-R DP Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...