In this post we’ll see a Java program to find the longest palindrome in the given string. In the given string there may be more than one palindromes but you need to find which one is the longest and display that one.
For finding the longest palindrome in the string you need to start from the middle of the string and move both left and right by one character and compare those characters, if those two character are equal that means you have a palindrome and you do the same thing for the next two characters. As example in string “98189” center is 1 and by moving both left and right and comparing you can see that 8 and 8 and then 9 and 9 are equal. At the same time center of the String also moves in the program as you have to find the longest palindrome in the String.
Another thing to consider is the case when String is even, in that case you will be taking two characters as center and then do the comparison of characters. The two characters considered as center should also be equal.
Java program to find the longest palindrome
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
public class LongestPal { public static void main(String[] args) { LongestPal lp = new LongestPal(); System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("12321981189")); System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("toppot")); System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101312321")); System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101311321")); } public String findLongestPalindrome(String str) { // starting point for comparison with other palindromes String longestPalindrome = str.substring(0, 1); for (int i = 0; i < str.length(); i = i+1) { // odd length case (center is i) String newPalindrome = checkIfEqual(str, i, i); if (newPalindrome.length() > longestPalindrome.length()) { longestPalindrome = newPalindrome; } // even length case (center is i, i+1) newPalindrome = checkIfEqual(str, i, i + 1); if (newPalindrome.length() > longestPalindrome.length()) { longestPalindrome = newPalindrome; } } return longestPalindrome; } public String checkIfEqual(String str, int begin, int end) { while ((begin >= 0 && end <= str.length() - 1) && (str.charAt(begin) == str.charAt(end))) { // move left begin--; // move right end++; } return str.substring(begin + 1, end); } } |
Output
|
1 2 3 4 |
Longest Palindrome- 981189 Longest Palindrome- toppot Longest Palindrome- 12321 Longest Palindrome- 3113 |
The time complexity of this solution is O(N2) and space complexity is O(1) as the same string is used and memory requirement in the program doesn’t increase.
That’s all for the topic Java Program to Find Longest Palindrome in The Given String. If something is missing or you have something to share about the topic please write a comment.
You may also like