Longest Palindromic Subsequence

Your task is to find the length of the longest palindromic subsequence in a given string S. A palindromic subsequence is a sequence that appears in the same relative order, but not necessarily contiguous, and reads the same backward as forward.

For example, consider the string abdbca. One of the longest palindromic subsequences is abdba which has a length of 5.

The problem can be formulated using dynamic programming. If we define dp[i][j] as the length of the longest palindromic subsequence in the substring S[i..j], then the recurrence is given by:

\(dp[i][j] = \begin{cases} 1 & \text{if } i = j,\\ 2 & \text{if } S[i] = S[j] \text{ and } j = i+1,\\ dp[i+1][j-1] + 2 & \text{if } S[i] = S[j],\\ \max(dp[i+1][j], dp[i][j-1]) & \text{if } S[i] \neq S[j]. \end{cases}\)

Note that the indices in the recurrence are based on 0-indexing.

inputFormat

The input consists of two lines. The first line contains a string S. The second line contains an integer N denoting the length of the string S.

outputFormat

Output a single integer representing the length of the longest palindromic subsequence in the string S.

abdbca
6

5