Longest Palindromic Subsequence - Practice Coding Problems

Longest Palindromic Subsequence - Problem

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For example, "ace" is a subsequence of "aec" (by removing 'e'), but "aec" is not a subsequence of "ace".

Input & Output

Example 1 — Basic Case

$ Input: s = "bbbab"

› Output: 4

💡 Note: One possible longest palindromic subsequence is "bbbb" (indices 0,1,2,4). We can also form "bbb" of length 3, but "bbbb" is longer.

Example 2 — All Different Characters

$ Input: s = "cbbd"

› Output: 2

💡 Note: One possible longest palindromic subsequence is "bb" (indices 1,2). Each single character is also a palindrome of length 1.

Example 3 — Single Character

$ Input: s = "a"

› Output: 1

💡 Note: The entire string "a" is a palindrome, so the longest palindromic subsequence has length 1.

Constraints

1 ≤ s.length ≤ 1000
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String "bbbab" - find longest palindromic subsequence

Process

Use DP to build solution from smaller substrings

Output

Length of longest palindromic subsequence

Key Takeaway

🎯 Key Insight: Build the solution by comparing characters at both ends and solving subproblems optimally

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

The key insight is that a palindromic subsequence either has matching characters at both ends or doesn't. We can solve this using 2D Dynamic Programming where dp[i][j] represents the longest palindromic subsequence in substring s[i...j]. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n²)	O(n²)	Use recursion with memoization to solve overlapping subproblems efficiently
2D Dynamic Programming	O(n²)	O(n²)	Build a 2D table where dp[i][j] represents longest palindrome in substring s[i...j]
Brute Force - Try All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check which ones are palindromes

Recursive with Memoization — Algorithm Steps

Compare characters at both ends of current substring
If equal, add 2 and solve for inner substring
If different, try excluding either end and take maximum
Use memoization to cache results

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare

Compare characters at both ends

Recurse

Solve smaller subproblems recursively

Cache

Store results to avoid recalculation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int memo[1001][1001];
int visited[1001][1001];

int dp(char* s, int left, int right) {
    if (left > right) return 0;
    if (left == right) return 1;
    
    if (visited[left][right]) {
        return memo[left][right];
    }
    
    int result;
    if (s[left] == s[right]) {
        result = 2 + dp(s, left + 1, right - 1);
    } else {
        int leftSkip = dp(s, left + 1, right);
        int rightSkip = dp(s, left, right - 1);
        result = (leftSkip > rightSkip) ? leftSkip : rightSkip;
    }
    
    memo[left][right] = result;
    visited[left][right] = 1;
    return result;
}

int solution(char* s) {
    int len = strlen(s);
    memset(visited, 0, sizeof(visited));
    return dp(s, 0, len - 1);
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of the n² subproblems is solved exactly once with memoization

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all n² subproblems plus recursion stack

⚠ Quadratic Space

85.0K Views

High Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler