8. Longest palindromic substring in a String

-

8. Longest palindromic substring in a String


Problem link :- click here


package programs;

public class String__8
{

	/*
		Longest palindrome in a string
				s = "aaaaabbaa"		ouput -->  aabbaa
				s = "abc"				ouput -->  a
		
		If we try it in brute force method it will be O( |s|^3 )
		|s|^2 to take the sub-String     and  |s|  to check is it palindrome
		
		there is a better option that is taking sub-String in just |s|
		
		to cover all the possible sub-array we have to take
		all possible sub-String by taking that element as center
		
		the sub-Strings taken above are only odd palinsromic sub-Strings
		there are also even palindromic sub-arrays, we shoould also 
		consider these sub-Strings 
		
		we must update the longest palindromic sub-String in both 
		the steps above
	*/
	
	static String longestPalindromicSubString(String s)
	{
		String long_str = new String();       //output
		
		//we will start from second element because you will not get 
		//any substring with first element as center (except itself)
		for(int i=1; i<s.length(); i++)
		{
			//odd palindromic substring
			int low = i;		//equal to 'i' because 
			int high = i;    	//every single character is also a palindrome
			
			while(   (  low >=0   &&    high < s.length()   )      &&   
				     (  s.charAt(low)  ==  s.charAt(high)  )                )
			{
				//updating long_str 
				if(   (high-low+1)  > long_str.length() )
					long_str = s.substring(low, high+1);
				
				low--;
				high++;
			}
			
			
			//even palindromic substring
			low = i-1;
			high = i;
			
			while(  (  low>=0    &&     high<s.length()   )    &&
				     ( s.charAt(low)  ==  s.charAt(high)  )               )
			{
				//updating long_str
				if( (high-low+1) > long_str.length() )
					long_str = s.substring(low, high+1);
				
				low--;
				high++;
			}
		}
		
		return long_str;
	}
	
	public static void main(String[] args)
	{
		String s = "aaaabbaa";
		String str = longestPalindromicSubString(s);
		System.out.println(str);
	}

}

Time complexity :-O()
Space complexity :- O()

Comments

Post a Comment

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

-
Image
4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...
Read more

1. Reverse

-
Image
1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...
Read more

3. Height of Binary tree

-
3. Height of Binary tree Problem link :- click here package Binary_Tree; public class BinaryTree__3 { static int heightOfTree(Node root) { if(root == null) return 0; int left_height = heightOfTree(root.left); int right_height = heightOfTree(root.right); return Math.max(left_height, right_height) + 1; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int arr[] = {2, -1, 3, -1, -1, 3}; tree.root = tree.createTree(arr, 0); int ans = heightOfTree(tree.root); System.out.println("Height : " + ans); } } Time complexity :- O(n) Space complexity :- O(n)
Read more