Blogs Hub

by Sumit Chourasia | Aug 29, 2020 | Category :coding | Tags : algorithm dynamic-programming leetcode

Longest Palindrome Subsequence - Dynamic Porgramming - MiniTV

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;

namespace LeetCode.AskGif.DP
{
    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);
                map.Add(GetKey(start, end), res);
                return res;
            }
            else
            {
                var res = Math.Max(
                    LongestPalindromeSubseqRecursion(s, start+1, end),
                    LongestPalindromeSubseqRecursion(s,start,end-1)
                    );
                map.Add(GetKey(start, end), res);
                return res;
            }
        }

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