As most people know, a palindrome string is one which reads the same backwards as it does forwards. English examples include “Madam, I’m Adam” and “racecar”.

Eagle-eyed readers will point out that the first of these is not, strictly speaking, a palindrome, for it contains a comma and an apostrophe and cannot therefore be regarded as a palindrome in a programming context.

In any case, palindrome checking is a very common challenge set for applicants during a tech job interview. Though this challenge might seem totally disconnected from practical reality, palindromes do occur in nature and it could be useful to know how to recognise them programmatically if you are dealing with biological data.

Our Approach

In this post we’re going to explore three different ways of solving this problem in Java. For the sake of simplicity we will assume that the string is predefined and there is no need to process user input. Although every solution presented here is technically O(n) in time complexity, we examine this in more detail in order to determine the best solution.

One Possible Solution

public static boolean isStringPalindrome(String str) {
  return str.equals(
    new StringBuilder(str)
    .reverse()
    .toString()
  );
}

We need to examine this algorithm more closely to get a better idea of how good its performance is in terms of time and space complexity. Measured using O(n) notation, this algorithm is O(n) i.e. linear. We will only focus on time complexity to keep things simple.

On closer consultation of the Java docs, it becomes clear that in the worst-case scenario - i.e. when the string is a palindrome - the time complexity equates to 3n + 16, the constant 16 term arising as a result of StringBuilder() freeing up 16 memory slots when creating a string.

Let’s see if we can do a little bit better than that.

A Second Possible Solution

Though the code here initially appears more complex than the previous solution, it does represent an improvement in terms of time complexity.

public static boolean isStringPalindrome(String str) {
  int n = str.length();
  for (int i = 0; i <= n; ++i) {
    if (str.charAt(i) !== str.charAt(n-i-1)) return false;
  }
  return true;
}

Considering the worst-case scenario, this program will iterate over the entire length of the string, implying a time complexity of n, since it makes exactly n inequality checks in this case.

A Third Possible Solution

However, there is actually no need to perform so many inequality checks. It is illogical to iterate over the entire length of the string as it is sufficient to compare the first half to the second half.

public static boolean isStringPalindrome(String str) {
  int n = str.length();
  for (int i = 0; i <= n/2; ++i) {
    if (str.charAt(i) !== str.charAt(n-i-1)) return false;
  }
  return true;
}

Hence we can implement the above solution which is n/2 in time complexity in the worst-case scenario (the string being a palindrome). If the length of the string is an odd number, this is reduced to (n - 1)/2.

We hope you enjoyed this article! Please feel free to reach out if you spotted any mistakes or would like to suggest an improvement 😊