Recursive palindrome check

Question

I'm trying to solve this which basically calls for a recursive palindrome check with some minor extra steps (Special characters and whitespace can be ignored). The test inputs' length can be 100000 characters.

I don't have access to the inputs but between 5 datasets my code fails in one of them to answer in under one second and throws a runtime error because it takes more than a second.

The rules of the challenge are to solve under one second with less than 128 MB of memory usage and it should be solved using a recursive algorithm.

So my question is how to increase the performance of this code/algorithm to make it faster.

public class Palindrome_308 {
 public static void main(String[] args) {
 var scanner = new Scanner(System.in);
 var isPalindrome = isPalindrome(scanner.nextLine().replaceAll("\\W", "").toLowerCase());
 if (isPalindrome) System.out.println("YES");
 else System.out.println("NO");
 }
 public static boolean isPalindrome(String input) {
 var length = input.length();
 if (length == 1) return true;
 if (length == 2) return input.charAt(0) == input.charAt(1);
 if (length == 3) return input.charAt(0) == input.charAt(2);
 if (input.charAt(0) != input.charAt(length - 1)) return false;
 return input.charAt(0) == input.charAt(length - 1) && isPalindrome(input.substring(1, length - 1));
 }
}

• Eric Stein: substring is expensive. Try passing indexes instead.
• Stormcloud: @Winston Ewert, What's the problem with recursion. Apart from the fact that the question requires recursion there are certain classes of problem that have short elegant recursive solutions and hideously complex iterative solutions.
• Stormcloud: @Winston Ewert, I'm questioning your comment because the OP did say "it should be solved using a recursive algorithm" (admittedly this is an odd requirement, and I don't think it's a good candidate for recursion, but...). Where do you see the improvements in performance? In my head the bigger worry is memory. The source string can be 100000 characters long, and if each pair of characters is one recursive call that is a lot of stack space. In addition each call creating a new String, so that is going to use a lot of heap space as well.
• Winston Ewert: @Stormcloud, I missed the requirement that it be recursive when I first read the question. If you are required to write a recursive solution, then obviously you've got to make the solution recursive. But that's just boring and doesn't seem worth further comment.
• Winston Ewert: @Stormcloud, but the biggest issue is surely creating new strings constantly.

Answer 1

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.

• greybeard: You could probably combine reduced object creation and call depth. I'm out of touch with Java microbenchmarking.

Answer 2

As Toby points out, your use of String.substring() is very expensive. It creates a new String object for each call, and (depending on the implementation of the String class) probably creates a new char array each time as well (some implementations allowed substrings to share that array with the original String, but I believe that's gone out of fashion).

Passing the original string and start/end indices will be much more efficient, as will Toby's suggestion of skipping over non-word characters rather than preprocessing the string.

As more general code review comments:

1. I'd remove the isPalindrome variable as it's unnecessary.
2. I'd brace all dependent clauses in the ifs.
3. I'd remove all the special cases - if you get the algorithm right, they're unnecessary and compared to the other costs in the program, save you too little to be worth while.
4. You test for equality of start and end characters twice. It's not necessary.

• TorbenPutkonen: I was in the impression that substring shared the underlying array, but as you say, it seems that this is no longer the case. I suppose the memory leaks were (quite rightly) considered to be a greater problem than the performance gain.

Answer 3

You are creating lots of strings. If you pass a view of the substring (i.e. pass a string reference and a pair of indices) into the recursive call, you will reduce your garbage creation to almost nil.

You could also eliminate the copy created by replaceAll(), by simply adjusting the indices to skip non-word characters before performing the equality test.