Smallest Palindromic Subsequence of Even Length in Range [ L , R ] | Java 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
import java . util . * ; class GFG { static int N = 100001 ; static int [ ] [ ] f = new int [ 26 ] [ N ] ; static void precompute ( String s , int n ) { for ( int i = 0 ; i < n ; i ++ ) { f [ s . charAt ( i ) - ' a ' ] [ i ] ++ ; } for ( int i = 0 ; i < 26 ; i ++ ) { for ( int j = 1 ; j < n ; j ++ ) { f [ i ] [ j ] += f [ i ] [ j - 1 ] ; } } } static int palindromicSubsequencesUtil ( int L , int R ) { int c = 0 , ok = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int cnt = f [ i ] [ R ] ; if ( L > 0 ) cnt -= f [ i ] [ L - 1 ] ; if ( cnt > 1 ) { ok = 1 ; c = i ; break ; } } if ( ok == 0 ) { return - 1 ; } return c ; } static void palindromicSubsequences ( int Q [ ] [ ] , int l ) { for ( int i = 0 ; i < l ; i ++ ) { int x = palindromicSubsequencesUtil ( Q [ i ] [ 0 ] , Q [ i ] [ 1 ] ) ; if ( x == - 1 ) { System . out . print ( - 1 + "NEW_LINE"); } else { char c = ( char ) ( ' a ' + x ) ; System . out . print ( ( char ) c + " " + ( char ) c + "NEW_LINE"); } } } public static void main ( String [ ] args ) { String str = " dbdeke " ; int Q [ ] [ ] = { { 0 , 5 } , { 1 , 5 } , { 1 , 3 } } ; int n = str . length ( ) ; int l = Q . length ; precompute ( str , n ) ; palindromicSubsequences ( Q , l ) ; } }