Longest palindrome substring in a string is a very common java interview question. To find out the longest palindrome in String, first of all, we need to identify the logic to do it.
The key point here is that from the mid of any palindrome string if we go to the right and left by 1 place, it’s always the same character. For example 12321, here mid is 3 and if we keep moving one position on both sides, we get 2 and then 1. We will use the same logic in our java program to find out the longest palindrome. However, if the palindrome length is even, the mid-size is also even. So we need to make sure in our program that this is also checked. For example, 12333321, here mid is 33 and if we keep moving one position in both sides, we get 3, 2 and 1.
In our java program, we will iterate over the input string with mid as 1st place and check the right and left character. We will have two global variables to save the start and the end position for palindrome. We also need to check if there is already a longer palindrome found since there can we multiple palindromes in the given string. Here is the final program that works fine for all the cases.
package com.journaldev.util;
public class LongestPalindromeFinder {
public static void main(String[] args) {
System.out.println(longestPalindromeString("1234"));
System.out.println(longestPalindromeString("12321"));
System.out.println(longestPalindromeString("9912321456"));
System.out.println(longestPalindromeString("9912333321456"));
System.out.println(longestPalindromeString("12145445499"));
System.out.println(longestPalindromeString("1223213"));
System.out.println(longestPalindromeString("abb"));
}
static public String intermediatePalindrome(String s, int left, int right) {
if (left > right) return null;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
// O(n^2)
public static String longestPalindromeString(String s) {
if (s == null) return null;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length() - 1; i++) {
//odd cases like 121
String palindrome = intermediatePalindrome(s, i, i);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
//even cases like 1221
palindrome = intermediatePalindrome(s, i, i + 1);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
}
return longest;
}
}
Below image shows the output of the above longest palindrome java program. We can improve the above code by moving the palindrome and longest lengths check into a different function. However, I have left that part for you. :) Please let me know if there are any other better implementations or if it fails in any case.
You can download the complete example code from our GitHub Repository.
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.
While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.
Hi, Thank you for this post, but your code doesn’t work for cases like: input: abb output should be bb, but your code gives a input: bb output should be bb, but your code gives b I couldn’t figure out why? Do you think it’s possible to make your code work for these two cases?
- Peihong
Hi, I think there is two bugs in the code above. 1. when checking the mid with size 2, the original code does not check the two characters in the mid. So left should be initialized to mid and right should be initialized to mid + 1. 2. the logic of expanding left and right is not correct. In the code above, when the left and right characters are not the same, it does not end the while loop, instead it just jump over them and keep going. It should change to: while (left >= 0 && right longestRight - longestLeft){ longestLeft = left; longestRight = right; } left–; right++; }
- Zhenxiang Liang
for input 1223213 i am getting answer as 122321. Am i missing something?
- abhijit
for input 1223213 i am getting answer as 122321. Am i missing something? please reply to me at gaikwad.abhijit@gmail.com
- abhijit
package Practice; import java.util.HashSet; public class Permutationwithplaindrome { /** * @param args */ public static void main(String[] args) { String str=“abcaaa”; HashSet hset = new HashSet(); for(int i=0;i<str.length();i++){ for(int j=i+1;j0){ for(int i=0,j=str.length()-1;i<=j;i++,j–){ if(str.charAt(i)==str.charAt(j)){ continue; }else return false; } return true; } return false; } }
- sandeep kumar
This is just wrong, you are finding for pairs of letters and if you find some pair, even if the others don’t match in between that pair of letters, you accept it as a palindrome
- Carlos
Thanks for all the comments, I have found out the bug in the code and update it to work fine in all the cases it was failing before.
- Pankaj
Hi, Please can you explain a bit more in detail how this has been done… Regards, Rishi Chopra.
- Rishi Chopra
Thanks brother but it has taken some time to understand. Eventhough we are not writing 2nd if loop we are getting answer for both even and odd strings.
- PRASADARAO
Q.The sum of two number without add operator and Any other utility utility fun and the answer given by Anuj k is helpful
- hthahseen