package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class Problem516 {
    public int longestPalindromeSubseq(String s) {
        return longestPalindromSubsequence(s, 0, "", new HashMap<>());
    }

    private static int longestPalindromSubsequence(String str, int idx, String accu,
                                                   Map<String, Integer> memo) {
        if (idx == str.length()) {
            if (isPalindrome(accu)) {
                return accu.length();
            }
            return 0;
        }
        String key = idx + "|" + accu;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int max = 0;
        if (isPalindrome(accu)) {
            max = accu.length();
        }
        int a = longestPalindromSubsequence(str, idx + 1, accu, memo);
        int b = longestPalindromSubsequence(str, idx + 1, accu + str.charAt(idx), memo);
        max = Math.max(max, Math.max(a, b));
        memo.put(key, max);
        return max;
    }

    private static boolean isPalindrome(String str) {
        for (int i = 0, j = str.length() - 1; i <= j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem516 prob = new Problem516();
//        System.out.println(prob.longestPalindromeSubseq("bbbab")); // 4
//        System.out.println(prob.longestPalindromeSubseq("cbbd")); // 2
//        System.out.println(prob.longestPalindromeSubseq("abacadae")); // 5
        System.out.println(prob.longestPalindromeSubseq("euazbipzncptldueeuechubrcourfpftcebikrxhybkymimgvldiwqvkszfycvqyvtiwfckexmowcxztkfyzqovbtmzpxojfofbvwnncajvrvdbvjhcrameamcfmcoxryjukhpljwszknhiypvyskmsujkuggpztltpgoczafmfelahqwjbhxtjmebnymdyxoeodqmvkxittxjnlltmoobsgzdfhismogqfpfhvqnxeuosjqqalvwhsidgiavcatjjgeztrjuoixxxoznklcxolgpuktirmduxdywwlbikaqkqajzbsjvdgjcnbtfksqhquiwnwflkldgdrqrnwmshdpykicozfowmumzeuznolmgjlltypyufpzjpuvucmesnnrwppheizkapovoloneaxpfinaontwtdqsdvzmqlgkdxlbeguackbdkftzbnynmcejtwudocemcfnuzbttcoew")); // 159
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -159,24 +159,88 @@
 String s) %7B%0A
+        Integer%5B%5D%5B%5D memo = new Integer%5Bs.length()%5D%5Bs.length()%5D;%0A
         retu
@@ -280,27 +280,28 @@
  0, 
-%22%22, new HashMap%3C%3E()
+s.length() - 1, memo
 );%0A 
@@ -378,23 +378,15 @@
 nt i
-dx, String accu
+, int j
 ,%0A  
@@ -437,28 +437,16 @@
     
- Map%3CString,
  Integer
 %3E me
@@ -445,9 +445,12 @@
 eger
-%3E
+%5B%5D%5B%5D
  mem
@@ -471,67 +471,37 @@
 f (i
-dx == str.length()) %7B%0A            if (isPalindrome(accu)) %7B
+ %3E j) %7B%0A            return 0;
 %0A   
@@ -501,32 +501,34 @@
  0;%0A        
+%7D%0A
         
 return accu.
@@ -519,43 +519,21 @@
     
-return accu.length();%0A            %7D
+if (i == j) %7B
 %0A   
@@ -540,33 +540,33 @@
          return 
-0
+1
 ;%0A        %7D%0A    
@@ -573,72 +573,30 @@
     
-String key = idx + %22%7C%22 + accu;%0A        if (memo.containsKey(key)
+if (memo%5Bi%5D%5Bj%5D != null
 ) %7B%0A
@@ -622,17 +622,14 @@
 memo
-.get(key)
+%5Bi%5D%5Bj%5D
 ;%0A  
@@ -673,88 +673,63 @@
 if (
-isPalindrome(accu)) %7B%0A            max = accu.length();%0A        %7D%0A        int a =
+str.charAt(i) == str.charAt(j)) %7B%0A            max = 2 +
  lon
@@ -759,28 +759,27 @@
 e(str, i
-dx
  + 1, 
-accu
+j - 1
 , memo);
@@ -791,564 +791,127 @@
     
-int b = longestPalindromSubsequence(str, idx + 1, accu + str.charAt(idx), memo);%0A        max = Math.max(max, Math.max(a, b));%0A        memo.put(key, max);%0A        return max;%0A    %7D%0A%0A    private static boolean isPalindrome(String str) %7B%0A        for (int i = 0, j = str.length() - 1; i %3C= j; i++, j--) %7B%0A            if (str.charAt(i) != str.charAt(j)) %7B%0A                return false;%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem516 prob = new Problem516();%0A//        System.out.println(prob.
+%7D else %7B%0A            max = Math.max(%0A                longestPalindromSubsequence(str, i + 1, j, memo),%0A                
 long
@@ -926,722 +926,98 @@
 drom
-e
 Subseq
-(%22bbbab%22)); // 4%0A//        System.out.println(prob.longestPalindromeSubseq(%22cbbd%22)); // 2%0A//        System.out.println(prob.longestPalindromeSubseq(%22abacadae%22)); // 5%0A        System.out.println(prob.longestPalindromeSubseq(%22euazbipzncptldueeuechubrcourfpftcebikrxhybkymimgvldiwqvkszfycvqyvtiwfckexmowcxztkfyzqovbtmzpxojfofbvwnncajvrvdbvjhcrameamcfmcoxryjukhpljwszknhiypvyskmsujkuggpztltpgoczafmfelahqwjbhxtjmebnymdyxoeodqmvkxittxjnlltmoobsgzdfhismogqfpfhvqnxeuosjqqalvwhsidgiavcatjjgeztrjuoixxxoznklcxolgpuktirmduxdywwlbikaqkqajzbsjvdgjcnbtfksqhquiwnwflkldgdrqrnwmshdpykicozfowmumzeuznolmgjlltypyufpzjpuvucmesnnrwppheizkapovoloneaxpfinaontwtdqsdvzmqlgkdxlbeguackbdkftzbnynmcejtwudocemcfnuzbttcoew%22)); // 159
+uence(str, i, j - 1, memo));%0A        %7D%0A        memo%5Bi%5D%5Bj%5D = max;%0A        return max;
 %0A   

Solve problem 516