# Blogs Hub

### by Sumit Chourasia | Aug 29, 2020 | Category :coding | Tags : algorithmdynamic-programmingleetcode

#### Longest Palindrome Subsequence - Dynamic Porgramming - मिनी टीवी

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".

Constraints:
1 <= s.length <= 1000
s consists only of lowercase English letters.

``````using System;
using System.Collections.Generic;
using System.Text;

{
public class LongestPalindromeSubseqSoln
{
Dictionary<string, int> map = new Dictionary<string, int>();
public int LongestPalindromeSubseq(string s)
{
return LongestPalindromeSubseqRecursion(s, 0, s.Length-1);
}

private int LongestPalindromeSubseqRecursion(string s, int start, int end)
{
if (map.ContainsKey(GetKey(start, end))){
return map[GetKey(start, end)];
}

if(start == end)
{
return 1;
}

if (s[start] == s[end])
{
if(start + 1 == end)
{
return 2;
}

var res = 2 + LongestPalindromeSubseqRecursion(s, start + 1, end - 1);
return res;
}
else
{
var res = Math.Max(
LongestPalindromeSubseqRecursion(s, start+1, end),
LongestPalindromeSubseqRecursion(s,start,end-1)
);
return res;
}
}

private string GetKey(int start, int end)
{
return \$"{start}-{end}";
}
}
}
``````

Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia