Your handling of base cases is somewhat redundant.
/** @return <code>input</code> is a palindrome. */
public static boolean isPalindrome(CharSequence input) {
var length = input.length();
if (length <= 1)
return true;
return input.charAt(0) == input.charAt(length - 1)
&& isPalindrome(input.subSequence(1, length - 1));
}
Short of passing indices in a recursive function, there seems to be only so much you can do to improve performance for longer sequences when reducing the string length by a constant in each call.
An attempt to limit object creation yielded moderate speed-up for intermediate lengths, but for longer strings latency of higher levels of the memory hierarchy seems to dominate:
/** memory conscious view into another CharSequence than can
* be shortened by one char on both ends simultaneously. */
static class SequenceView implements CharSequence, Cloneable {
final CharSequence viewed;
int start = 0, length;
public SequenceView(CharSequence viewed) {
this.viewed = viewed;
length = viewed.length();
}
@Override
public int length() { return length; }
@Override
public char charAt(int index) {
if (index < 0 || length <= index)
throw new IllegalArgumentException();
return viewed.charAt(index + start);
}
@Override
public CharSequence subSequence(int start, int end) {
if (start < 0 || end < start || this.start + length < end)
throw new IllegalArgumentException();
SequenceView sv = new SequenceView(viewed);
sv.start = this.start + start;
sv.length = end - start;
return sv;
}
/** @return a <code>CharSequence</code> containing
* the former contents of <code>this</code> without
* the first and last character.
* To this end, <code>this</code> is returned (and
* modified, obviously). Consider yourself warned! */
CharSequence mid() {
if (length < 2)
throw new IllegalStateException();
start += 1;
length -= 2;
return this;
}
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
/** @return <code>input</code> is a palindrome. */
public static boolean isPalindrome(CharSequence input) {
SequenceView sv = input instanceof SequenceView
? (SequenceView) input : new SequenceView(input);
return sv.length() <= 1 ||
sv.charAt(0) == sv.charAt(sv.length() - 1)
&& isPalindrome(sv.mid());
}
Well, the key in in getting complexity of a superlinear algorithm down in divide&conquer is to reduce problem size by a factor not too small.
Trying with sequences half the size:
/** @return input
is a palindrome. */
public static boolean isPalindrome(CharSequence input) {
int length = input.length();
if (length <= 3)
return length <= 1 || input.charAt(0) == input.charAt(length - 1);
int l4 = length / 4;
// palindrome if inner half is and concatenation of outer quarters
return isPalindrome(input.subSequence(l4, length - l4))
&& isPalindrome(new StringBuilder(input.subSequence(0, l4))
.append(input.subSequence(length - l4, length)));
}
There should never be sequences on the stack with more than twice the input characters all told.
substring
is expensive. Try passing indexes instead. \$\endgroup\$