Longest Palindromic Subsequence

medium

Acceptance: 51%

Dynamic Programming

Given a string, compute the length of its longest subsequence that reads the same forwards and backwards. Characters in the subsequence need not be adjacent in the original string.

Examples

Example 1:

Input:s = "character"

Output:5

Explanation: One longest palindromic subsequence is "carac" with length 5.

Example 2:

Input:s = "abcdef"

Output:1

Explanation: No two characters form a palindrome, so the best is any single character.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Longest Palindromic Subsequence

Examples

Hints

Related Problems