# Longest Palindromic Substring challenge

My code is a mix-up between dynamic programming with the HashMap and brute force with the way I reach out the results and substring. I don't know how to optimize my algorithm without googling and looking for already solved solutions with different approaches.

class Solution {
public String longestPalindrome(String s) {
if (s.length() > 1000) return "";
if (s.length() == 0) return "";
HashSet<String> hs = new HashSet<>();
int size = 1;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++)
{
for (int j = i; j < s.length() - 1; j++)
{
String ss = s.substring(i, j+2);
int ssl = ss.length();
if (hs.contains(ss))
{
if (ssl > size) {
size = ssl;
longest = ss;
}
}
else{
if (isPalindrome(ss)){
hs.add(ss);
if (ssl > size) {
size = ssl;
longest = ss;
}
}
}
}
}
return longest;
}

public boolean isPalindrome(String s) {
int j = s.length() - 1;
int i = 0;
while (i < j){
if (s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}


The webpage where this problem is posted says the max size of the string can be 1000. However if a string of that size is the input the algorithm takes 200-210 ms to execute and return the substring.

I'm 100% sure it works, but it's slow.

• Why are you not using algorythm from en.wikipedia.org/wiki/Longest_palindromic_substring ? The optimal solution is O(n), yours is O(n^2) just from 2 for loops and either of isPalindrome() or String.substring()  push it to O(n^3). – user158037 Oct 8 '18 at 10:17