package leetcode;

/**
 * https://leetcode.com/problems/longest-palindromic-substring/
 */
public class Problem5 {
    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        String longest = "";
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            String p = palindrome(chars, i, true);
            if (p.length() > longest.length()) {
                longest = p;
            }
            p = palindrome(chars, i, false);
            if (p.length() > longest.length()) {
                longest = p;
            }
        }
        return longest;
    }

    private String palindrome(char[] chars, int idx, boolean even) {
        int left = idx;
        int right = idx;
        if (!even) {
            if (idx - 1 >= 0 && idx + 1 < chars.length && chars[idx - 1] == chars[idx + 1]) {
                left--;
                right++;
            } else if (idx + 1 < chars.length && chars[idx] == chars[idx + 1]) {
                right++;
            } else {
                return "";
            }
        } else {
            if (idx + 1 < chars.length && chars[idx] == chars[idx + 1]) {
                right++;
            } else if (idx - 1 >= 0 && idx + 1 < chars.length && chars[idx - 1] == chars[idx + 1]) {
                left--;
                right++;
            } else {
                return "";
            }
        }
        while (left >= 0 && right < chars.length) {
            if (chars[left] != chars[right]) {
                break;
            }
            left--;
            right++;
        }
        left++;
        right--;
        return new String(chars, left, right - left + 1);
    }
}

@@ -168,70 +168,153 @@
     
-if (s.length() == 1) %7B%0A            return s;%0A   
+String%5B%5D%5B%5D memo = new String%5Bs.length() + 1%5D%5Bs.length() + 1%5D;%0A        return longestPalindrome(s, 0, s.length(), memo);%0A
     
- 
 %7D
+%0A
 %0A    
-   
+private static
  Str
@@ -328,159 +328,117 @@
 gest
- = %22%22;%0A        char%5B%5D chars = s.toCharArray();%0A        for (int i = 0; i %3C chars.length; i++) %7B%0A            String p = palindrome(chars, i, true);%0A
+Palindrome(String s, int i, int j, String%5B%5D%5B%5D memo) %7B%0A        if (i %3E= j) %7B%0A            return %22%22;%0A    
     
+%7D%0A
     
@@ -449,173 +449,145 @@
 if (
-p.length() %3E longest.length()) %7B%0A                longest = p;%0A            %7D%0A            p = palindrome(chars, i, false);%0A            if (p.length() %3E longest.length(
+memo%5Bi%5D%5Bj%5D != null) %7B%0A            return memo%5Bi%5D%5Bj%5D;%0A        %7D%0A        String answer = s.substring(i, j);%0A        if (isPalindrome(answer
 )) %7B
@@ -603,38 +603,55 @@
     
-    
-longest = p;%0A            %7D
+memo%5Bi%5D%5Bj%5D = answer;%0A            return answer;
 %0A   
@@ -648,32 +648,39 @@
 nswer;%0A        %7D
+ else %7B
 %0A        return 
@@ -676,465 +676,276 @@
     
-return longest;%0A    %7D%0A%0A    private String palindrome(char%5B%5D chars, int idx, boolean even) %7B%0A        int left = idx;%0A        int right = idx;%0A        if (!even) %7B%0A            if (idx - 1 %3E= 0 && idx + 1 %3C chars.length && chars%5Bidx - 1%5D == chars%5Bidx + 1%5D) %7B%0A                left--;%0A                right++;%0A            %7D else if (idx + 1 %3C chars.length && chars%5Bidx%5D == chars%5Bidx + 1%5D) %7B%0A                right++;%0A            %7D else %7B%0A                return %22%22
+    answer = %22%22;%0A        %7D%0A        String a = longestPalindrome(s, i + 1, j, memo);%0A        String b = longestPalindrome(s, i, j - 1, memo);%0A        String c = longestPalindrome(s, i + 1, j - 1, memo);%0A        if (answer.length() %3C a.length()) %7B%0A            answer = a
 ;%0A  
@@ -942,36 +942,32 @@
 er = a;%0A        
-    
 %7D%0A        %7D else
@@ -964,213 +964,118 @@
     
-%7D else %7B%0A            if (idx + 1 %3C chars.length && chars%5Bidx%5D == chars%5Bidx + 1%5D) %7B%0A                right++;%0A            %7D else if (idx - 1 %3E= 0 && idx + 1 %3C chars.length && chars%5Bidx - 1%5D == chars%5Bidx + 1%5D
+if (answer.length() %3C b.length()) %7B%0A            answer = b;%0A        %7D%0A        if (answer.length() %3C c.length()
 ) %7B%0A
@@ -1090,165 +1090,201 @@
     
-  
-  left--;%0A                right++;%0A            %7D else %7B%0A                return %22%22;%0A            %7D%0A        %7D%0A        while (left %3E= 0 && right %3C chars.length
+answer = c;%0A        %7D%0A        memo%5Bi%5D%5Bj%5D = answer;%0A        return answer;%0A    %7D%0A%0A    private static boolean isPalindrome(String s) %7B%0A        for (int i = 0, j = s.length() - 1; i %3C= j; i++, j--
 ) %7B%0A
@@ -1303,35 +1303,34 @@
 if (
+s.
 char
-s%5Bleft%5D
+At(i)
  != 
+s.
 char
-s%5Bright%5D
+At(j)
 ) %7B%0A
@@ -1349,169 +1349,65 @@
     
-b
 re
-ak;%0A            %7D%0A            left--;%0A            right++;%0A        %7D%0A        left++;%0A        right--;%0A        return new String(chars, left, right - left + 1)
+turn false;%0A            %7D%0A        %7D%0A        return true
 ;%0A  

Update problem 5