Table of contents
1.
Introduction
2.
Understanding Palindromes
2.1.
Approach to Find Palindromic Sub-Strings
2.2.
Java Code
2.3.
Detailed Explanation
2.4.
Time Complexity
3.
Frequently Asked Questions
3.1.
Q: Can this code handle a single character as a palindrome?
3.2.
Q: What's the time complexity of this solution?
3.3.
Q: Can this code be optimized further?
4.
Conclusion
Last Updated: Mar 27, 2024

Java Program to Find All Palindromic Sub-Strings of a String

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). Finding palindromic sub-strings within a given string is a fascinating problem and has applications in various domains including bioinformatics and text processing.

Java Program to Find All Palindromic Sub-Strings of a String

In this article, we will explore a Java program that finds all palindromic sub-strings of a given string.

Read More, addition of two numbers in java

Understanding Palindromes

Before diving into the code, let's understand what a palindrome is. A palindrome is a sequence of characters that reads the same backward as forward. For example, "madam" or "racecar" are palindromes.

Also read palindrome number in python.

Approach to Find Palindromic Sub-Strings

We can approach this problem using the following steps:

  • Iterate Through the String: We'll need to go through each character of the string.
     
  • Expand Around the Center: For every character, we'll expand around it and check if the characters are the same on both sides.
     
  • Count and Store: If it's a palindrome, we count and store it.
  •  

Here's the complete Java code to find all palindromic sub-strings of a given string:

  • Java Code

Java Code

public class PalindromicSubStrings {

    

    public static void main(String[] args) {

        String input = "madam";

        findPalindromicSubStrings(input);

    }




    public static void findPalindromicSubStrings(String input) {

        if (input == null || input.length() < 1) return;




        System.out.println("Palindromic sub-strings are:");

        for (int center = 0; center <= 2 * input.length() - 1; center++) {

            int left = center / 2;

            int right = left + center % 2;

            while (left >= 0 && right < input.length() && input.charAt(left) == input.charAt(right)) {

                System.out.println(input.substring(left, right + 1));

                left--;

                right++;

            }

        }

    }

}
You can also try this code with Online Java Compiler
Run Code

This code will output:

Palindromic sub-strings are:

m
a 
d
ada
madam
a
m
output

Also check, Palindrome string

Detailed Explanation

Loop through Each Character: The outer loop for (int center = 0; center <= 2 * input.length() - 1; center++) iterates through each character, and for each character, it treats it as a center.
 

Expand Around Center: The inner loop while (left >= 0 && right < input.length() && input.charAt(left) == input.charAt(right)) expands around the center. If the characters at the left and right are equal, it's part of a palindrome.
 

Print the Palindrome: Inside the inner loop, we print the palindrome using input.substring(left, right + 1).

Time Complexity

The time complexity of this approach is O(n2)  where 

n is the length of the string. This is because, in the worst case, we may end up checking 

n characters around each center.

Also see, Java Ioexception and Eclipse ide for Java Developers

Frequently Asked Questions

Q: Can this code handle a single character as a palindrome?

 Yes, every single character is considered a palindrome, and this code will recognize that.

Q: What's the time complexity of this solution?

The time complexity is O(n2)

Q: Can this code be optimized further?

There are more advanced algorithms like Manacher's Algorithm that can find all palindromic sub-strings in linear time, i.e.,

O(n).

Conclusion

Finding all palindromic sub-strings of a given string is an engaging problem that can be solved using the expand-around-center technique. Though our solution is simple and easy to understand, there are more complex algorithms available for optimization. Understanding such problems not only enhances algorithmic thinking but also sets the foundation for solving real-world problems where pattern recognition plays a vital role.

You can also consider our paid courses such as DSA in Java to give your career an edge over others!

Happy Learning!

Live masterclass