💻 Longest Palindromic Subsequence with DP
Unlock the symmetrical heart of sequences using dynamic programming — input a string and reveal the length of its longest palindromic subsequence!
🔬 The Sequence Symmetrist's Quest
🎯 The Challenge:
In biological data analysis or text correction systems, finding the most stable or symmetrical parts of a sequence is very useful. A palindromic subsequence is a sequence that reads the same forwards and backwards, but not necessarily contiguous.
📋 Problem:
Your task is to help analyze the stability of a given sequence by identifying its longest palindromic subsequence. Print the length of the LPS.
Problem Specifications
- Input: A single line containing string S (1 ≤ |S| ≤ 1000, uppercase English letters).
- Output: A single integer — the length of the longest palindromic subsequence.
Example: Input 1
Output: 4 (e.g., "A G T A")
🔄 Dynamic Programming Strategy
Key Idea
- dp[i][j] = length of LPS in S[i..j].
- Base: dp[i][i] = 1 (single char).
- 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]).
- 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 Finder
Enter string and press Compute
Examples
AGGTAB
→ 4
A
→ 1
📊 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