Queries to check if substring [ L ... R ] is palindrome or not | Python3 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
N = 100 NEW_LINE def pre_process ( dp , s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT dp [ i ] [ j ] = False NEW_LINE DEDENT DEDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT for i in range ( n - j + 1 ) : NEW_LINE INDENT if ( j <= 2 ) : NEW_LINE INDENT if ( s [ i ] == s [ i + j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ i + j - 1 ] = True NEW_LINE DEDENT DEDENT elif ( s [ i ] == s [ i + j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ i + j - 1 ] = dp [ i + 1 ] [ i + j - 2 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def answerQuery ( l , r , dp ) : NEW_LINE INDENT if ( dp [ l ] [ r ] ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT s = " abaaab " NEW_LINE dp = [ [ 0 for i in range ( N ) ] for i in range ( N ) ] NEW_LINE pre_process ( dp , s ) NEW_LINE queries = [ [ 0 , 1 ] , [ 1 , 5 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT answerQuery ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , dp ) NEW_LINE DEDENT