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
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
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.
Related Posts
- Java Programs For Displaying Patterns
- How to Convert String to Byte Array in Java
- How to Convert String to int in Java
- Java Program to Reverse a String In-place
- Find Length of String Without Using length() Method in Java
- Java Program to Swap Two Numbers Without Using Third Variable
- How to Create a Deadlock in Java
- Java Program to Convert Date to LocalDate, LocalDateTime
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
