Find Longest Palindrome in sub string

Given a string, find the longest substring which is palindrome. For example, if the given string is “abacdfgdcaba”, the output should be “aba”.

Logic: 

  1. One by one consider every character as center point of even and length palindromes For loop.
  2. Find the longest even length palindrome with center points as i-1 and i. (First While Loop).
  3. Find the longest odd length palindrome with center point as i.  (Second While Loop)
package com.tuturself.programs;


public class LongestPalindrome {

	public static void main (String [] args){
		String str = "abacdfgdcaba";
		longestPalindromeSubstr(str);

	}

	private static void longestPalindromeSubstr(String str) {
		int maxLength = 1;  // The result (length of LPS)

		int start = 0;
		int len = str.length();
		char [] charString = str.toCharArray();
		int low, high;

		for (int i = 1; i < len; ++i)
		{
			low = i - 1;
			high = i;
			while (low >= 0 && high < len && charString[low] == charString[high])
			{
				if (high - low + 1 > maxLength)
				{
					start = low;
					maxLength = high - low + 1;
				}
				--low;
				++high;
			}

			low = i - 1;
			high = i + 1;
			while (low >= 0 && high < len && charString[low] == charString[high])
			{
				if (high - low + 1 > maxLength)
				{
					start = low;
					maxLength = high - low + 1;
				}
				--low;
				++high;
			}
		}

		System.out.println("Longest palindrome substring is== ");
		printString(str, start, start + maxLength - 1);

	}

	private static void printString(String str, int low, int high){
		for( int i = low; i <= high; ++i )
			System.out.print(str.toCharArray()[i]);
	}
}


Output:
Longest palindrome substring is== 
aba

 

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself