Smallest Palindromic Subsequence of Even Length in Range [ L , R ] | Python3 program to find lexicographically smallest palindromic subsequence of even length ; Frequency array for each character ; Preprocess the frequency array calculation ; Frequency array to track each character in position 'i ; Calculating prefix sum over this frequency array to get frequency of a character in a range [ L , R ] . ; Util function for palindromic subsequences ; Find frequency of all characters ; For each character find it 's frequency  in range [L, R] ; If frequency in this range is > 1 , then we must take this character , as it will give lexicographically smallest one ; There is no character in range [ L , R ] such that it 's frequency is > 1. ; Return the character 's value ; Function to find lexicographically smallest palindromic subsequence of even length ; Find in the palindromic subsequences ; No such subsequence exists ; Driver Code ; Function calls
N = 100001 NEW_LINE f = [ [ 0 for x in range ( N ) ] for y in range ( 26 ) ] NEW_LINE def precompute ( s , n ) : NEW_LINE ' NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT f [ ord ( s [ i ] ) - ord ( ' a ' ) ] [ i ] += 1 NEW_LINE DEDENT for i in range ( 26 ) : NEW_LINE INDENT for j in range ( 1 , n ) : NEW_LINE INDENT f [ i ] [ j ] += f [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT def palindromicSubsequencesUtil ( L , R ) : NEW_LINE INDENT ok = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT cnt = f [ i ] [ R ] NEW_LINE if ( L > 0 ) : NEW_LINE INDENT cnt -= f [ i ] [ L - 1 ] NEW_LINE DEDENT if ( cnt > 1 ) : NEW_LINE INDENT ok = 1 NEW_LINE c = i NEW_LINE break NEW_LINE DEDENT DEDENT if ( ok == 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return c NEW_LINE DEDENT def palindromicSubsequences ( Q , l ) : NEW_LINE INDENT for i in range ( l ) : NEW_LINE INDENT x = palindromicSubsequencesUtil ( Q [ i ] [ 0 ] , Q [ i ] [ 1 ] ) NEW_LINE if ( x == - 1 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT c = ord ( ' a ' ) + x NEW_LINE print ( 2 * chr ( c ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " dbdeke " NEW_LINE Q = [ [ 0 , 5 ] , [ 1 , 5 ] , [ 1 , 3 ] ] NEW_LINE n = len ( st ) NEW_LINE l = len ( Q ) NEW_LINE precompute ( st , n ) NEW_LINE palindromicSubsequences ( Q , l ) NEW_LINE DEDENT