## Leetcode 5 "Longest Palindromic Substring"

January 1, 0001

5. Longest Palindromic Substring

## Result

LTE

``````class Solution {
int[][] arr;
String result = "";
public String longestPalindrome(String s) {
arr = new int[s.length()+1][s.length()+1];

for(int i=0; i<s.length(); i++) {
longestPalindromeAux(s, i, i+1);
}
return result;
}

public int longestPalindromeAux(String s, int from, int to) {
if(to > s.length()) {
return -1;
}

if(from < 0) {
return -1;
}

if(arr[from][to] != 0) {
return arr[from][to];
}

String thisString = s.substring(from, to);
if(!isPalindrome(thisString)) {
return -1;
}

if(result.length() < thisString.length())
result = thisString;

int r1 = longestPalindromeAux(s, from, to+1);

int r2 = longestPalindromeAux(s, from-1, to);

int r3 = longestPalindromeAux(s, from-1, to+1);

arr[from][to] = Math.max(r1, Math.max(r2, r3));
return arr[from][to];
}

// Map<String, Boolean> map = new HashMap<>();
boolean isPalindrome(String s) {
// if(map.containsKey(s))
//     return map.get(s);
int l = 0;
int r = s.length()-1;
while(l < r) {
if(s.charAt(l)  != s.charAt(r)) {
// map.put(s, false);
return false;
}
l = l+1;
r = r-1;
}
// map.put(s, true);
return true;
}
}
``````