Smallest Palindromic Subsequence of Even Length in Range [ L , R ] | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 100001 ; int f [ 26 ] [ N ] ; void precompute ( string s , int n ) { for ( int i = 0 ; i < n ; i ++ ) { f [ s [ i ] - ' a ' ] [ i ] ++ ; } for ( int i = 0 ; i < 26 ; i ++ ) { for ( int j = 1 ; j < n ; j ++ ) { f [ i ] [ j ] += f [ i ] [ j - 1 ] ; } } } int palindromicSubsequencesUtil ( int L , int R ) { int c , 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 ; } void palindromicSubsequences ( int Q [ ] [ 2 ] , int l ) { for ( int i = 0 ; i < l ; i ++ ) { int x = palindromicSubsequencesUtil ( Q [ i ] [ 0 ] , Q [ i ] [ 1 ] ) ; if ( x == -1 ) { cout << -1 << " STRNEWLINE " ; } else { char c = ' a ' + x ; cout << c << c << " STRNEWLINE " ; } } } int main ( ) { string str = " dbdeke " ; int Q [ ] [ 2 ] = { { 0 , 5 } , { 1 , 5 } , { 1 , 3 } } ; int n = str . size ( ) ; int l = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ; precompute ( str , n ) ; palindromicSubsequences ( Q , l ) ; return 0 ; }