Longest Palindromic Subsequence

An interactive, step-by-step visualisation of Longest Palindromic Subsequence.

Category

Dynamic Programming

Time complexity

O(n²)

Space complexity

O(n²)

Pseudocode

dp[i][i] = 1
if s[i]==s[j]: dp[i][j] = dp[i+1][j-1] + 2
else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Reference implementation

def lps(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (2 if length == 2 else dp[i+1][j-1] + 2)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

Open the interactive Longest Palindromic Subsequence visualisation →