🚀

End of Year Sale: Use Coupon Code END2025 to Get Extra 25% Off.

02DAYS
:
21HOURS
:
57MINUTES
:
12SECONDS

Leetcode Problem 516. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence

Leetcode Solutions

Approach: Recursive Dynamic Programming

  1. Initialize n to the length of s.
  2. Create a 2D array memo with dimensions n x n, initialized with zeros.
  3. Define a recursive function lps that takes parameters i, j, and memo.
    • If memo[i][j] is not zero, return its value (memoization).
    • If i > j, return 0 (base case: empty substring).
    • If i == j, return 1 (base case: single character substring).
    • If s[i] == s[j], set memo[i][j] to 2 + lps(i + 1, j - 1, memo).
    • Otherwise, set memo[i][j] to max(lps(i, j - 1, memo), lps(i + 1, j, memo)).
  4. Return the result of lps(0, n - 1, memo).
UML Thumbnail

Approach: Iterative Dynamic Programming

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...