#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/interval-dp/lps-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/interval-dp/lps-implementation

Repovive

LeetCode 516 Longest Palindromic Subsequence - Implementation - Interval DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 516 Longest Palindromic Subsequence - Implementation

The code

Here's the solution:

function longestPalindromeSubseq(s)
    n := length of s
    dp := 2D (two-dimensional) array of size n × n, initialized to 0
    // Base case: single characters
    for i from 0 to n - 1
        dp[i][i] := 1
    // Fill by increasing length
    for len from 2 to n
        for i from 0 to n - len
            j := i + len - 1
            if s[i] = s[j] then
                dp[i][j] := dp[i + 1][j - 1] + 2
            else
                dp[i][j] := max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

Time: $O(n^2)$ . Space: $O(n^2)$ . This is the standard interval DP pattern: iterate by length, compute shorter ranges first.

Time complexity: $O(n^2)$ .

Space complexity: $O(n^2)$ .