# Optimized n-square solution in Java

• Maybe this is a "greedy" way to find solution:
len = length of s;
Try to find a palindrome of length = len,
then length len-1, len-2, ...
Whenever we find one, this is the largest one, and we don't need to check the rest.

``````/**
* when i see "longest", i think of optimization or greedy.
* don't want to try every possibility and then return
* longest one, that will be guaranteed n-square.
*
* try len=s.lenth(),
* then len-1, len-2, until len=0.
* whenever i find a palindrome of length len, this is the longest one.
*/
public String longestPalindrome(String s) {
char[] chars = s.toCharArray();
int len = s.length();
while (len >= 0) {
for (int i = 0; i + len - 1 < chars.length; i++) {
int left = i;
int right = i + len - 1;
boolean good = true;
while (left < right) {
if (chars[left] != chars[right]) {
good = false;
break;
}
left++;
right--;
}
if (good)
return s.substring(i, i + len);
}
--len;
}

return "";
}``````

• beautiful optimization,it is faster than dp

• This is an n-cube solution
The number of operations required is sum{i * (n+1-i)} from i=1 through n

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.