Introduction

Longest Palindromic Subsequence (LPS) is one of the most important String Dynamic Programming problems.

You are given:

string s

Goal:

Find the length of the longest palindromic subsequence.

Important:

Subsequence ≠ Substring

A subsequence can skip characters while maintaining order.

Example

s = "bbbab"

Output:

4

Explanation:

 "bbbb"Length = 4

Key Observation

For every substring:

s[i...j]

Two possibilities exist.

Case 1

s[i] == s[j]

Then both characters can be used.

dp[i][j] = 2 + dp[i+1][j-1]

Case 2

s[i] != s[j]

Skip one side.

dp[i][j] = max(dp[i+1][j],dp[i][j-1])

DP State

dp[i][j] = Length of Longest Palindromic Subsequence
inside s[i...j]

Dry Run

Input:

s = "bbbab"

Important Palindrome:

bbbb

Length:

4

Answer:

4

Approach 1 : Memoization

Explanation

For every substring:

  1. Compare both ends.
  2. Match → Use both.
  3. No Match → Skip one side.
  4. Store result.
  5. Reuse calculations.

Approach 2 : Tabulation

Explanation

State:

dp[i][j]

Transition:

If match
2 + inner answer

Else
max(left, right)

Build table from:

Small substrings → Large substrings

Practice

Complexity Analysis

MemoizationTime Complexity: O(n²)
Space Complexity: O(n²)

Tabulation
Time Complexity: O(n²)
Space Complexity: O(n²)

Why This Problem is Important

  • String DP
  • Interval DP
  • Palindrome Problems
  • State Transitions
  • LCS Relationship

Common Beginner Mistakes

  • Confusing substring with subsequence
  • Wrong DP traversal order
  • Missing length = 2 case
  • Using greedy approach
  • Incorrect interval handling

Interview Tip

Always explain:

If both ends match take both

Otherwise:

Skip left or Skip right

This is the core Interval DP idea.

Related Questions

  • Palindromic Substrings
  • Longest Palindromic Substring
  • Word Break
  • Edit Distance
  • Longest Common Subsequence

Final Takeaway

Longest Palindromic Subsequence is one of the most important String Dynamic Programming problems.

It teaches:

  • Interval DP
  • String DP
  • State Design
  • Optimal Substructure

Mastering LPS builds a strong foundation for advanced palindrome and interval-based DP interview questions.