Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Longest Palindromic Subsequence

Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Uber

Print the length of the longest subsequence of s that is a palindrome.

Input

One string s (lowercase letters).

Output

The length.

Constraints

It equals the LCS of s and reverse(s).

Example 1

Input

bbbab

Output

4

Example 2

Input

cbbd

Output

2

Hints

  1. A palindromic subsequence of s reads the same in s and in reverse(s).
  2. So the answer is LCS(s, reverse(s)). (Or interval DP: dp[i][j] = dp[i+1][j−1] + 2 if s[i] == s[j], else max(dp[i+1][j], dp[i][j−1]).)

Approach

Any palindromic subsequence of s is a common subsequence of s and its reverse. The reverse also holds: the longest common subsequence of s and reverse(s) has the same length as the longest palindromic subsequence. So run the standard LCS DP with two rows on s and reverse(s). This is about 10^6 cells for |s| = 1000.

Complexity: O(n²) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string a;
    cin >> a;
    string b(a.rbegin(), a.rend());
    int n = a.size();
    vector<int> prev(n + 1, 0), cur(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cur[j] = (a[i - 1] == b[j - 1]) ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    cout << prev[n] << "\n";
    return 0;
}

Python solution

a = input().strip()
b = a[::-1]
n = len(a)
prev = [0] * (n + 1)
for ch in a:
    cur = [0] * (n + 1)
    for j in range(1, n + 1):
        if ch == b[j - 1]:
            cur[j] = prev[j - 1] + 1
        else:
            cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
    prev = cur
print(prev[n])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = new StringBuilder(a).reverse().toString();
        int n = a.length();
        int[] prev = new int[n + 1], cur = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
            int[] t = prev; prev = cur; cur = t;
        }
        System.out.println(prev[n]);
    }
}

Solve Longest Palindromic Subsequence online · All practice problems