## Longest Palindrome In A String

Ran across the Longest Palindrome In A String problem today and tried it out. Saw that there is a linear solution but have yet to try it out. I’ll be trying that out next once I make sense of it.

```	boolean isPalindrome(String text)
{
boolean result = false;
StringBuilder sb = new StringBuilder(text);

StringBuilder sbReverse = sb.reverse();

int res = (sb.toString().compareTo(text) );
return (sb.toString().compareTo(text) ) == 0;
}

String naive1(String text) {
String result;

for (int i = text.length(); i >= 2; i--) {
for (int j = text.length()-i; j >= 0; j--) {
if (isPalindrome(text.substring(j,i))) {
return text.substring(j, i);
}
}
}

return "";
}```

```	// Returns the longest palindrome around this position
String longestPalindrome(String text, int position) {
int len = text.length();
int left, right;
StringBuilder sb = new StringBuilder();
// test position out of bounds
if (position < 0 || position >= len)
return null;
// test if position is one less than length
if (position == 0 || position == len-1)
return sb.append(text.charAt(position)).toString();
// if length is even
if (len % 2 == 0) {
left = position;
right = position+1;
} else { // odd
sb.append(text.charAt(position));
left = position - 1;
right = position + 1;
}
do {
char cLeft = text.charAt(left);
if (cLeft == text.charAt(right)) {
sb.insert(0, cLeft);
sb.append(cLeft);
left--;
right++;
}
else
break;

} while (left >= 0 && right < len);
return sb.toString();
}

String result = null;
StringBuffer max = new StringBuffer();
for (int i = 0; i < text.length(); i++) {
int maxLen = max.length();
String palin = longestPalindrome(text, i);
if (palin.length() > maxLen) {
max.delete(0, maxLen);
max.append(palin);
}

}
return max.toString();
}```
This entry was posted in Coding. Bookmark the permalink.