💻 Longest Palindromic Subsequence Length with DP

Dive into dynamic programming to extract the symmetrical core of strings — input a sequence and compute the length of its longest palindromic subsequence!

🔬 The Symmetry Engineer's Mission

🎯 The Challenge:

As a senior software engineer, you have been tasked with developing a program that uses dynamic programming to find the length of the Longest Palindromic Subsequence (LPS) in a given string.

📋 Problem:

Implement a function to find the longest palindromic subsequence that takes a string as input and returns an integer representing the length of the longest palindromic subsequence in the given string.

Problem Specifications

  • Input: A single line containing a string (1 ≤ |S| ≤ 100, English alphabets).
  • Output: A single integer — the length of the longest palindromic subsequence.

Example: Input 1

Output: 5 (the whole "madam" is palindromic)

🔄 Dynamic Programming Strategy

Key Idea

  1. dp[i][j] = length of LPS in S[i..j].
  2. Base: dp[i][i] = 1 (single char).
  3. If S[i] == S[j], dp[i][j] = dp[i+1][j-1] + 2.
  4. Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  5. Fill table by increasing length (j - i).

Note: Result is dp[0][n-1]. Time: O(n^2).

DP Table

Time: O(n^2)
Space: O(n^2)

Recursive (Naive)

O(2^n) — exponential, too slow

🔍 Step-by-Step DP Demo

Ready. Use controls below to start demo.

Input String

DP Table State (LPS lengths i to j)

LPS length will appear here

Progress Tracker

1. Initialize diagonal (length 1: all 1)
2. Fill length 2 substrings
3. For length L > 2: check ends
4. If match, add 2 to inner LPS
5. Else, max of skip left or right
6. Track global max

🎮 Build Your LPS Length Calculator

Enter string and press Compute

Examples

madam
→ 5
mam
→ 3

📊 Analysis & Optimization

Time

O(n^2)

Fill n x n table in O(1) per cell.

Space

O(n^2)

DP table; optimizable to O(n) with 2 rows.

Optimization Ideas

  • Use two 1D arrays to reduce space to O(n).
  • For very long strings, consider memoized recursion if sparse.
  • In C++, use vector> for table; fast input for n=100.