Leetcode Problem 1682. Longest Palindromic Subsequence II

1682. Longest Palindromic Subsequence II

Leetcode Solutions

Dynamic Programming withD Memoization

  1. Initialize a 3D array dp with dimensions [s.length()][s.length()][26] to store the longest palindromic subsequences.
  2. Iterate over all possible substrings of s by using two nested loops, with i going from s.length() - 1 to 0 and j going from i + 1 to s.length() - 1.
  3. For each substring s[i...j], iterate over all possible previous characters k from 0 to 25.
  4. If s[i] equals s[j] and s[i] is not equal to the character represented by k, update dp[i][j][s[i] - 'a'] to be the maximum of its current value and dp[i + 1][j - 1][k] + 2.
  5. Update dp[i][j][k] to be the maximum of dp[i][j][k], dp[i + 1][j][k], and dp[i][j - 1][k] to inherit the previous maximum length wrapped by character k.
  6. After filling the dp array, the answer is the maximum value in dp[0][s.length() - 1].
UML Thumbnail

Dynamic Programming withD Memoization

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...