Longest Palindromic Subsequence

Medium
578.

Longest Palindromic Subsequence

Longest Palindromic Subsequence is a medium coding problem on strings and dynamic programming, asked in Amazon, Adobe and Uber interviews.

Given a string s, return the length of its longest palindromic subsequence.

A subsequence is formed by deleting zero or more characters without reordering the rest.

Example 1

Input
s = "bbbab"
Output
4
Explanation
One answer is "bbbb".

Example 2

Input
s = "cbbd"
Output
2
Explanation
"bb".

Example 3

Input
s = "a"
Output
1

Constraints

  • 1 <= s.length <= 300
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Palindromic Subsequence — Problem & Solution

Longest Palindromic Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Palindromic Subsequence is a medium coding problem on strings and dynamic programming, asked in Amazon, Adobe and Uber interviews.

  • Difficulty: Medium
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Adobe, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a string s, return the length of its longest palindromic subsequence.

A subsequence is formed by deleting zero or more characters without reordering the rest.

Example 1

Input: s = "bbbab"
Output: 4
Explanation: One answer is "bbbb".

Example 2

Input: s = "cbbd"
Output: 2
Explanation: "bb".

Example 3

Input: s = "a"
Output: 1

Constraints

  • 1 <= s.length <= 300
  • s consists of lowercase English letters.

Hints for Longest Palindromic Subsequence

  1. Hint 1

    Define dp[i][j] as the answer for the substring s[i..j].

  2. Hint 2

    If the ends match, they can both join a palindrome built from the inside: dp[i+1][j-1] + 2.

  3. Hint 3

    Otherwise drop one end or the other and take the better result.

How to solve Longest Palindromic Subsequence

Interval DP over substrings. Matching endpoints extend an inner palindrome by two; mismatched endpoints force a choice of which one to discard.

Approach

  1. Let dp[i][j] be the longest palindromic subsequence of s[i..j], with dp[i][i] = 1.
  2. Fill i from n-1 down to 0 so that dp[i+1][…] is already known.
  3. When s[i] == s[j], set dp[i][j] = dp[i+1][j-1] + 2.
  4. Otherwise set dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  5. Return dp[0][n-1].

Why it works

If the two ends match, there is always an optimal solution that uses both — swapping them in never shortens the answer. If they differ, at most one can appear in the palindrome, so the best solution omits one end.

Complexity

  • Time — O(n²)
  • Space — O(n²), reducible to O(n)

Pitfalls

  • Filling i upward reads dp[i+1][j-1] before it is computed.
  • For a two-character match, dp[i+1][j-1] refers to an empty range and must be 0 — the zero-initialised table handles it.
  • This is not the same as the longest palindromic substring, which must be contiguous.

Reference solution

Python

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            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])
    return dp[0][n - 1] if n else 0

Java

public static int longestPalindromeSubseq(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

C++

int longestPalindromeSubseq(string s) {
    int n = (int) s.size();
    if (n == 0) return 0;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            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]);
        }
    }
    return dp[0][n - 1];
}

JavaScript

var longestPalindromeSubseq = function(s) {
    const n = s.length;
    if (n === 0) return 0;
    const dp = [];
    for (let i = 0; i < n; i++) dp.push(new Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i + 1; j < n; j++) {
            if (s.charAt(i) === s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming