There is a significant improvement that can be made to this algorithm.

As it is, when there are a long sequence of repeating characters: "aaaaaa"

this algorithm repeats the work twice for each position.

Instead of expanding twice, once from [i,i] and a second from [i,i+1], we can do it once and start from [i,j] where we find j by scanning right from i where charAt(i) == charAt(i-1).

By doing this, for "baaaaaab", instead of trying over and over for each index. we try i=0 and dont get far, but when i=1 we search ahead to j=6 and we expand(s, 1,6).

I found this to be way way faster. In fact its closer to O(N) for long repeated sequences as opposed to N^2.

Here's my example

https://discuss.leetcode.com/topic/103658/optimized-java-search-and-expand-solution