My Solution Is Naive, It Cost O(n^2), Is there Any Solution faster?

There is an O(n) algorithm called Manacher's algorithm, explained here in detail. However, it is a nontrivial algorithm, and no one expects you to come up with this algorithm in a 30 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.

The trivial solution refers to the brute force method which has o(n^3) cost and o(1) auxiliary space.
One can improve upon time complexity by applying Dynamic programming technique thus reducing the time complexity to o(n^2), but on the down side the DP algo has auxiliary space complexity of o(n^2).
One can further improve upon this by reducing the space complexity to o(1), the following method has time complexity of o(n^2) and space complexity of o(1), which out performs dynamic programming method in terms of space complexity. In this program all possible palindromes of odd and even length are generated and at the end the longest palindrome if exists is returned.class Solution { public: string longestPalindrome(string s) { int start = 0; int maxLength = 1; string res; if(s.length()==1) return s; int low, high; for (int i = 1; i < s.length(); ++i) { low = i  1; high = i; while (low >= 0 && high < s.length() && s[low] == s[high]) { if (high  low + 1 > maxLength) { start = low; maxLength = high  low + 1; } low; ++high; } low = i  1; high = i + 1; while (low >= 0 && high <s.length() && s[low] == s[high]) { if (high  low + 1 > maxLength) { start = low; maxLength = high  low + 1; } low; ++high; } } res = s.substr(start,maxLength); return res; } };

Manacher Algorithm O(n) algorithm, this algorithm achieves linear time complexity by taking the advantage of the certain characteristics or observations about a palindrome and a subpalindrome
public class Solution { public static String longestPalindrome(String s) { if (s==null  s.length()==0) return ""; char[] s2 = addBoundaries(s.toCharArray()); int[] p = new int[s2.length]; int c = 0, r = 0; // Here the first element in s2 has been processed. int m = 0, n = 0; // The walking indices to compare if two elements are the same for (int i = 1; i<s2.length; i++) { if (i>r) { p[i] = 0; m = i1; n = i+1; } else { int i2 = c*2i; if (p[i2]<(ri)) { p[i] = p[i2]; m = 1; // This signals bypassing the while loop below. } else { p[i] = ri; n = r+1; m = i*2n; } } while (m>=0 && n<s2.length && s2[m]==s2[n]) { p[i]++; m; n++; } if ((i+p[i])>r) { c = i; r = i+p[i]; } } int len = 0; c = 0; for (int i = 1; i<s2.length; i++) { if (len<p[i]) { len = p[i]; c = i; } } char[] ss = Arrays.copyOfRange(s2, clen, c+len+1); return String.valueOf(removeBoundaries(ss)); } private static char[] addBoundaries(char[] cs) { if (cs==null  cs.length==0) return "".toCharArray(); char[] cs2 = new char[cs.length*2+1]; for (int i = 0; i<(cs2.length1); i = i+2) { cs2[i] = ''; cs2[i+1] = cs[i/2]; } cs2[cs2.length1] = ''; return cs2; } private static char[] removeBoundaries(char[] cs) { if (cs==null  cs.length<3) return "".toCharArray(); char[] cs2 = new char[(cs.length1)/2]; for (int i = 0; i<cs2.length; i++) { cs2[i] = cs[i*2+1]; } return cs2; } }
reference Manacher Algorithm

This is my code using Dynamic Programming which has a running time and space cost of O(n*n).
public class Solution { public String longestPalindrome(String s) { int left=0; int max=0; int len=s.length(); int right=len1; boolean huiwen[][]=new boolean[len][len]; for(int i=0;i<len;++i) { for(int j=0;j<=i;++j) { if(i j>=2 ) { if(s.charAt(i)==s.charAt(j)&& huiwen[j+1][i1]) { huiwen[j][i]=true; } else { huiwen[j][i]=false; } } else { if(i==j) { huiwen[i][i]=true; } else { if(s.charAt(i)==s.charAt(j)) { huiwen[j][i]=true; } else { huiwen[j][i]=false; } } } if(ij+1>=max && huiwen[j][i]) { max=ij+1; left=j; right=i; } } } return s.substring(left,right+1); } }