# Easy java solution with O(1) space and O(n^2) time

• The basic idea is to traverse all the palindromes with its pivot range from the first char of string s to the last char of string s (consider both even length and odd length situation). Use StringBuilder to minimize the space complexity. Here is the code, feast yourself:

``````public class Solution {
StringBuilder longest = new StringBuilder("");

public String longestPalindrome(String s) {
if (s.length() <= 1) return s;

for (int i = 0; i < s.length(); i++) {
expand(s, longest, i, i); //odd
expand(s, longest, i, i + 1); //even
}

return longest.toString();
}

private void expand(String s, StringBuilder longest, int i, int j) {
while (i >= 0 && j < s.length()) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i + 1 > longest.length()) {
longest.delete(0, longest.length());
longest.append(s.substring(i, j + 1));
}
i--;
j++;
}
else
break;
}
}
``````

}

• Thanks, very easy, a modified version without StringBuiler, accepted with 214 ms.

``````    public class Solution {
private int maxLength = 1;
private int maxIndex = 0;
public String longestPalindrome(String str) { //O(N^2), space O(1)
int length = str.length();
for (int i=0; i<length; i++) {
// find longest odd palindrome with center i
findPalindrome(str, length, i, 0);
// find longest even palindrome with center i
findPalindrome(str, length, i, 1);
}
return str.substring(maxIndex, maxIndex+maxLength);
}

private void findPalindrome(String str, int length, int i, int shift) {
int left = i;
int right= i+shift;
while (left >= 0 && right < length && str.charAt(left) == str.charAt(right)) {
if ((right - left + 1) > maxLength) {
maxLength = right - left + 1;
maxIndex = left;
}
left--;
right++;
}
}

}
``````

• Thanks for your answer, but the space is O(N).

• it is not a good idea to manage the stringbuilder here, the "delete" operation makes your complexity goes to O(n^3)

• ``````public String longestPalindrome(String s) {
int index = 0;
int length = 1;
for (int i = 0; i < s.length(); i++) {
// 类型1的回文 baab 形式
if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
int templen = 2;
int tempindex = i;
for (int m = i - 1, n = i + 2; m >= 0 && n < s.length(); m--, n++) {
if (s.charAt(m) == s.charAt(n)) {
templen += 2;
tempindex = m;
} else {
break;
}
}

if (templen > length) {
length = templen;
index = tempindex;
}
}
if (i + 1 < s.length() && i-1 >=0 && s.charAt(i-1) == s.charAt(i + 1)) {
int templen = 1;
int tempindex =i-1 ;
for(int m=i-1, n =i+1; m >= 0 && n < s.length(); m--, n++ ) {
if (s.charAt(m) == s.charAt(n)) {
templen += 2;
tempindex = m;
} else {
break;
}
}

if (templen > length) {
length = templen;
index = tempindex;
}
}
}

return s.substring(index, length+index);
}``````

• feel not good to define the maxLength and maxIndex to be a private variable... It might cause synchronization problem when this object is invoked by multiple instances.

• They are instance variables so why would they have synchronization issues ?

• This solution works better than upper solution.

• This is not O(n^2) .This is O(n^3) because s.substring is linear operation in Java 7.

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