Queries to check if substring [ L ... R ] is palindrome or not | javascript implementation of the approach ; Pre - processing function ; Get the size of the string ; Initially mark every position as false ; For the length ; Iterate for every index with length j ; If the length is less than 2 ; If characters are equal ; Check for equal ; Function to answer every query in O ( 1 ) ; Driver code
var N = 100 ; function pre_process ( dp , s ) { var n = s . length ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = false ; } } for ( j = 1 ; j <= n ; j ++ ) { for ( i = 0 ; i <= n - j ; i ++ ) { if ( j <= 2 ) { if ( s [ i ] == s [ i + j - 1 ] ) { dp [ i ] [ i + j - 1 ] = true ; } } else if ( s [ i ] == s [ i + j - 1 ] ) { dp [ i ] [ i + j - 1 ] = dp [ i + 1 ] [ i + j - 2 ] ; } } } } function answerQuery ( l , r , dp ) { if ( dp [ l ] [ r ] ) { document . write ( " " ) ; } else { document . write ( " " ) ; } } var s = " " ; var dp = Array ( N ) . fill ( ) . map ( ( ) => Array ( N ) . fill ( ) ) ; pre_process ( dp , s ) ; var queries = [ [ 0 , 1 ] , [ 1 , 5 ] ] ; var q = queries . length ; for ( i = 0 ; i < q ; i ++ ) { answerQuery ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , dp ) ; }