Minimum insertions to form shortest palindrome | Java program to find minimum number of insertions on left side to form a palindrome . ; Returns true if a string str [ st . . end ] is palindrome ; Returns count of insertions on left side to make str [ ] a palindrome ; Find the largest prefix of given string that is palindrome . ; Characters after the palindromic prefix must be added at the beginning also to make the complete string palindrome ; Driver Code
import java . util . * ; class GFG { static boolean isPalin ( char [ ] str , int st , int end ) { while ( st < end ) { if ( str [ st ] != str [ end ] ) return false ; st ++ ; end -- ; } return true ; } static int findMinInsert ( char [ ] str , int n ) { for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( isPalin ( str , 0 , i ) ) return ( n - i - 1 ) ; } return 0 ; } public static void main ( String [ ] args ) { char [ ] Input = " JAVA " . toCharArray ( ) ; System . out . println ( findMinInsert ( Input , Input . length ) ) ; } }