Leetcode Problem 730. Count Different Palindromic Subsequences

730. Count Different Palindromic Subsequences

Leetcode Solutions

Dynamic Programming (usingD array)

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

Dynamic Programming (usingD array)

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...