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)); } } 

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.

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.

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.