Palindrome In Java

A string is said to be a palindrome if it reads the same from the beginning and the end. All characters appear in the same sequence when read from the start or the end of the string. Some examples of palindromes are "Bob", "Naman", "Racecar", "Deed", etc.

In this tutorial, we will learn how to check whether a string is a palindrome or not.

Solution 1: Using Two Pointers

We can use two pointers to check if a string is a palindrome. One pointer will start from the beginning of the string and will move in the forward direction. The second pointer starts at the end of the string and moves in the backward direction. At each iteration, if the characters present at the two pointers are the same, then we will move the pointers. Otherwise, we will return false. We will also convert the input string to lowercase.

public class Demo
{
	public static boolean isPalindrome(String str)
	{
		int startIdx = 0;
		int endIdx = str.length() - 1;		
		while(startIdx < endIdx)
		{
			char start = str.charAt(startIdx);
			char end = str.charAt(endIdx);
			if(Character.toLowerCase(start) != Character.toLowerCase(end))
				return false;
			startIdx += 1;
			endIdx -= 1;
		}
		return true;
	}	
	public static void main(String[] args)
	{
		System.out.println("racecar is palindrome: " + isPalindrome("racecar"));
		System.out.println("RaCeCar is palindrome: " + isPalindrome("RaCeCar"));
		System.out.println("naman is palindrome: " + isPalindrome("naman"));
		System.out.println("Deed is palindrome: " + isPalindrome("Deed"));
		System.out.println("Java is palindrome: " + isPalindrome("Java"));
	}
}

racecar is palindrome: true
RaCeCar is palindrome: true
naman is palindrome: true
Deed is palindrome: true
Java is palindrome: false

Find Palindrome using Recursive Approach

We can implement the above code recursively. There can be two base cases for the recursion:

• If the string contains a single character, then return true.

• If at any point the start pointer and end pointer characters are not equal, then return false.

The complete code for the recursive solution is shown below.

public class Demo
{
	public static boolean isPalindrome(String str)
	{
		String lowercaseStr = str.toLowerCase();
		
		return isPalindromeRecursive(lowercaseStr, 0, lowercaseStr.length() - 1);
	}
	
	public static boolean isPalindromeRecursive(String str, int startIdx, int endIdx)
	{
		if(startIdx == endIdx)//Single character string
			return true;
		
		if(str.charAt(startIdx) != str.charAt(endIdx))
			return false;
		
		if(startIdx < endIdx + 1)
			return isPalindromeRecursive(str, startIdx + 1, endIdx - 1);
		
		return true;
	}
	
	public static void main(String[] args)
	{
		System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
		System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
		System.out.println("naman is a palindrome: " + isPalindrome("naman"));
		System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
		System.out.println("Java is a palindrome: " + isPalindrome("Java"));
	}
}

racecar is a palindrome: true
RaCeCar is a palindrome: true
naman is a palindrome: true
Deed is a palindrome: true
Java is a palindrome: false

Solution 2: Reversing the String

We can use the StringBuilder or StringBuffer class to reverse the input string. If the reversed string is the same as the original one, then it is a palindrome.

We can manually reverse the string by traversing the string in the opposite direction(right to left).

public static boolean isPalindrome(String str)
{
	String lowercaseStr = str.toLowerCase();
	StringBuilder reverseSB = new StringBuilder();
	//Reversing the string
	for(int i = lowercaseStr.length() - 1; i >= 0; i--)
		reverseSB.append(lowercaseStr.charAt(i));
		
	String reversedStr = reverseSB.toString();
	return lowercaseStr.equals(reversedStr);
}

Or we can use the reverse() method of the StringBuilder class.

public static boolean isPalindrome(String str)
{
	String lowercaseStr = str.toLowerCase();
	
	StringBuilder sb = new StringBuilder(lowercaseStr);
	StringBuilder reversedSB = sb.reverse();//Reversing the string
		
	String reversedStr = reversedSB.toString();
	return lowercaseStr.equals(reversedStr);
}

Let's test this approach on some strings and view the outputs.

public static void main(String[] args)
{
	System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
	System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
	System.out.println("naman is a palindrome: " + isPalindrome("naman"));
	System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
	System.out.println("Java is a palindrome: " + isPalindrome("Java"));
}

racecar is a palindrome: true
RaCeCar is a palindrome: true
naman is a palindrome: true
Deed is a palindrome: true
Java is a palindrome: false

Solution 3: Using Java 8 Streams

The Stream API can also be used to check for palindrome strings. We will use the IntStream class to iterate through the string. Next, we will use the noneMatch() method and a predicate.

import java.util.stream.IntStream;

public class Demo
{
	public static boolean isPalindrome(String str)
	{
		String lowercaseStr = str.toLowerCase();
		return IntStream.range(0, lowercaseStr.length() / 2)
					   .noneMatch(i -> lowercaseStr.charAt(i) != lowercaseStr.charAt(lowercaseStr.length() - i - 1));
	}
	
	public static void main(String[] args)
	{
		System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
		System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
		System.out.println("naman is a palindrome: " + isPalindrome("naman"));
		System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
		System.out.println("Java is a palindrome: " + isPalindrome("Java"));
	}
}

racecar is a palindrome: true
RaCeCar is a palindrome: true
naman is a palindrome: true
Deed is a palindrome: true
Java is a palindrome: false

Summary

In this tutorial, we discussed the different ways in which we can check if a string is a palindrome. We can use a simple two-pointer approach. This method can be implemented iteratively or recursively. We can also reverse the string and check whether the reversed string is the same as the original. Java 8 streams can also be used.

Reversing the string will always give a time complexity of O(n). The two-pointer approach, on the other hand, performs better and returns a best-case time complexity of O(1). The best case for the two-pointer method occurs when the characters at the two extremes of the string do not match. The worst-case time complexity of the two-pointer approach is O(n).