Core Java coding question on palindrome

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. What is a palindrome?
A. A palindrome is a word or sentence that reads the same forward as it does backward. For example, the terms "racecar", "dad", "madam" and the name "Hannah". The longest palindromic substring of "bananas" is "anana" -- the left side of a palindrome is a mirror image of its right side.

  //loop from left to right  
    for (int i = 0; i < s.length() - 1; i++) {
  if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
   return false;
  }
 }
 
 return true;

"anana" is a palindrome.

i = 0 --> a != a : false
i = 1 --> n != n : false
i = 2 --> a != a : false
i = 3 --> n != n : false
i = 4 --> break the loop

Alternatively, the reversed string must match the original string.

      String reverse = "";

      //loop from right to left
      for ( int i = length - 1 ; i >= 0 ; i-- ) {
         reverse = reverse + s.charAt(i);
   }
 
      if (s.equals(reverse)) {
        return true;
   } 
   else {
        return false;
   }

We don't actually have to process all the characters, and can stop in the middle

package com.java8.examples;

public class PalindromeTest {

 public static void main(String[] args) {
  System.out.println("Is madam a Palindrome? " + isPalindrome("madam"));
 }

 public static boolean isPalindrome(String s) {
  boolean result = false;

  int i, begin, end, middle;

  begin = 0;
  end = s.length() - 1;
  middle = (begin + end) / 2;

  //process from left to middle
  for (i = begin; i <= middle; i++) {
   if (s.charAt(begin) == s.charAt(end)) {
    begin++;
    end--;
   } else {
    break;
   }
  }

  //if has gone past the middle
  if (i == middle + 1) {
   result = true;
  }

  return result;
 }
}

Q. How will you find the longest palindrome of a given string?
A. Algorithm: Have 2 center pointers, and move  one to the left and the other to the right. Cater for 2 scenarios where you have odd number of characters and even number of characters as shown below.

package com.java8.examples;

public class PalindromeLongestSubstring {
 
  private static String findLongestPalindrome(String s){
  if(s == null || s.length() == 1){
   return s;
  }
  
  String longest = s.substring(0,1);
  
  for (int i = 0; i < s.length(); i++) {
   //one center. odd number of characters (e.g 12321)
   String result = findPalindromeForGivenCenter(s, i, i);
   longest = result.length() > longest.length()? result : longest;
   
   //two centers. even number of characters (e.g 123321)
   result = findPalindromeForGivenCenter(s, i, i+1);
   longest = result.length() > longest.length()? result : longest;
  }
  
  return longest;
 }
 
 
 
 // Given either same left and right center (e.g.12321) or 
 // 2 left and right centers  (e.g. 123321) find the longest palindrome
 private static String findPalindromeForGivenCenter (final String s, int leftCenter, int rightCenter) {
  int length = s.length();
  
  while (leftCenter >= 0 && rightCenter <= length -1 && s.charAt(leftCenter) == s.charAt(rightCenter)) {
   leftCenter--;  //move from center to left
   rightCenter++; //move from center to right 
  }
  
  //leftCenter+1 because the index would have moved left before exiting the above loop
  return s.substring(leftCenter+1,rightCenter);
 }

}

Test the output for different inputs

        public static void main(String[] args) {
  String s1 = "12321", s2= "123321", s3 = "71233218", s4="1234", s5="88123217";
  System.out.println(s1  + " = " + findLongestPalindrome(s1));
  System.out.println(s2  + " = " + findLongestPalindrome(s2));
  System.out.println(s3  + " = " + findLongestPalindrome(s3));
  System.out.println(s4  + " = " + findLongestPalindrome(s4));
  System.out.println(s5  + " = " + findLongestPalindrome(s5));
  
  String s6 = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
  System.out.println(s6  + " = " + findLongestPalindrome(s6));
  
 }

Output:

12321 = 12321
123321 = 123321
71233218 = 123321
1234 = 1
88123217 = 12321
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE = 12345678987654321