Print longest palindrome word in a sentence in Java
A palindrome is a word, phrase, number, or sequence of characters that reads the same backward as forward. In the context of finding the longest palindrome word in a string, it refers to identifying the longest word in the string that remains unchanged when read backward.
Example:
Input: String s = "A racecar driver won ten races"
Output: Longest Palindrome word: racecar
Explanation: "racecar" is the longest palindrome word in the given sentence.
Approach: Brute Force
Algorithm
Step 1: Defines a function isPalindrome() to check if a given string is a palindrome.
Step 2: Splits the input string into individual words using whitespace as a delimiter.
Step 3: Iterates through each word and check if it's a palindrome using the isPalindrome() function.
Step 4: Updates the longest palindrome word found so far.
Step 5: Prints the longest palindrome word found, or "No Palindrome Word" if none is found.
FileName: LongestPalindromeWord.java
public class LongestPalindromeWord { // Function to check if a substring is palindrome static boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; // Convert the string to lowercase for case-insensitive comparison str = str.toLowerCase(); while (left < right) { if (str.charAt(left) != str.charAt(right)) return false; left++; right--; } return true; } // Function to find the longest palindrome word static String longestPalindrome(String str) { String[] words = str.split("\s+"); // Split the string into words String longestPalindromeWord = ""; for (String word : words) { if (isPalindrome(word) && word.length() > longestPalindromeWord.length()) { longestPalindromeWord = word; } } return longestPalindromeWord; } // Driver code public static void main(String args[]) { String s = "A racecar driver won ten races"; String longestPalindromeWord = longestPalindrome(s); // Retain the original capitalization of the longest palindrome word if (longestPalindromeWord.isEmpty()) System.out.println("No Palindrome Word"); else { // Find the index of the longest palindrome word in a case-insensitive manner int index = s.toLowerCase().indexOf(longestPalindromeWord.toLowerCase()); // Get the original longest palindrome word using the found index String originalLongestPalindromeWord = s.substring(index, index + longestPalindromeWord.length()); System.out.println("Longest Palindrome word: " + originalLongestPalindromeWord); } } }
Output:
Longest Palindrome word: racecar
Complexity Analysis: The time complexity is O(n*m), where n is the number of words in the input string and m is the average length of the words. The space complexity is O(1) as it uses no additional data structures that grow with the input size.
Approach: Iterative
Algorithm
Step 1: The isPalindrome() method verifies whether a given word is a palindrome by comparing characters from both ends to the middle.
Step 2: The main function iterates through each word in the input sentence, extracting them character by character until a space is encountered.
Step 3: For each word parsed, it checks if it's a palindrome using the isPalindrome() method.
Step 4: If a palindrome word is found and its length surpasses the length of the previously detected longest palindrome word, it updates the longest palindrome word found so far.
Step 5: After processing all words, it prints the longest palindrome word found or "No Palindrome Word" if none is found.
FileName: LongestPalindromeWord1.java
import java.util.*; public class LongestPalindromeWord1 { // Function to check if a word is a palindrome static boolean isPalindrome(String word) { int n = word.length(); word = word.toLowerCase(); // Convert word to lowercase for case-insensitive comparison for (int i = 0; i < n; i++, n--) { if (word.charAt(i) != word.charAt(n - 1)) { return false; } } return true; } // Function to find the longest palindrome word static String longestPalindromeWord(String str) { str = str + " "; // Add a space at the end to handle the last word String longestWord = "", word = ""; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (ch != ' ') { word = word + ch; // Build the word character by character } else { // Check if the word is a palindrome and longer than the current longest palindrome word if (isPalindrome(word) && word.length() > longestWord.length()) { longestWord = word; // Update longestWord if a longer palindrome is found } word = ""; // Reset word for the next word } } return longestWord; // Return the longest palindrome word found } public static void main(String[] args) { String sentence = "A racecar driver won ten races"; String longestPalindrome = longestPalindromeWord(sentence); if (longestPalindrome.isEmpty()) { System.out.println("No Palindrome Word"); } else { System.out.println("Longest palindrome word: " + longestPalindrome); } } }
Output:
Longest Palindrome word: racecar
Complexity Analysis: The time complexity and the space complexity remain the same as the brute force approach.