# Optimized Java search and expand solution.

• Your standard Search and Expand with a twist.
Search and Expand like you see in many solutions with:
expand(s, i, i);
expand(s, i, i+1);
These don't deal with repeating characters very well, like: "baaaaaab"
it would try index 0 to 7. for index 1 to 6 it would repeatedly try to expand and fail, sometimes iterating pretty far before detecting failure. We can greatly improve that and reduce our "expands" call to 1 instead of 2.
Instead upon index 1, scan forward while charAt(index+1) == charAt(index).
Now we have our left and right bounds to expand from.
So now we try:
expands(s,l,r) where l=index, and r=the rightmost consecutive matching character.

This proves to be much much faster in repeating character cases.

``````class Solution {
public String longestPalindrome( String s ) {
if (s == null)
return "";
int len = s.length();
if (len < 2)
return s;
if (len < 3) {
if (s.charAt( 0 ) == s.charAt( 1 )) {
return s;
} else {
return s.substring( 0, 1 );
}
}
int ll = 0;
int lr = 0;

int[] out = new int[2];
for (int l = 0; l < s.length() - 1; l++) {
// advance the right cursor while the character matches the prev
// this allows us to not double, triple+ count duplicate letter sequences
// it also allows us to deal with the case where the adjacent letter or letters are equal in the center of a palindrome
char prev = l > 0 ? s.charAt( l - 1 ) : '\0';
char c = s.charAt( l );
int r = l;
if (c != prev) {
while (r < s.length() - 1 && s.charAt( r ) == c) {
r++;
}
if (s.charAt( r ) != c)
r--;
}

// expand outward from l and r
expand( s, l, r, out );
if (lr - ll < out[1] - out[0]) {
ll = out[0];
lr = out[1];
}
l = r;
}

return s.substring( ll, lr + 1 );
}

private void expand( String s, int l, int r, int[] out ) {
while (l > 0 && r < s.length() - 1 && s.charAt( l ) == s.charAt( r )) {
l--;
r++;
}
if (s.charAt( l ) != s.charAt( r )) {
l++;
r--;
}
out[0] = l;
out[1] = r;
}
``````

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