Check if a substring can be Palindromic by replacing K characters for Q queries | C ++ program for the above approach ; Function to find whether string can be made palindromic or not for each queries ; To store the count of ith character of substring str [ 0. . . i ] ; Current character ; Update dp [ ] [ ] on the basis recurrence relation ; For each queries ; To store the count of distinct character ; Find occurrence of i + ' a ' ; Half the distinct Count ; If half the distinct count is less than equals to K then palindromic string can be made ; Driver Code ; Given string str ; Given Queries ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void canMakePaliQueries ( string str , vector < vector < int > > & Q ) { int n = str . length ( ) ; vector < vector < int > > dp ( 26 , vector < int > ( n , 0 ) ) ; for ( int i = 0 ; i < 26 ; i ++ ) { char currentChar = i + ' a ' ; for ( int j = 0 ; j < n ; j ++ ) { if ( j == 0 ) { dp [ i ] [ j ] = ( str [ j ] == currentChar ) ; } else { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + ( str [ j ] == currentChar ) ; } } } for ( auto query : Q ) { int left = query [ 0 ] ; int right = query [ 1 ] ; int k = query [ 2 ] ; int unMatchedCount = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int occurrence = dp [ i ] [ right ] - dp [ i ] [ left ] + ( str [ left ] == ( i + ' a ' ) ) ; if ( occurrence & 1 ) unMatchedCount ++ ; } int ans = unMatchedCount / 2 ; if ( ans <= k ) { cout << " YES STRNEWLINE " ; } else { cout << " NO STRNEWLINE " ; } } } int main ( ) { string str = " GeeksforGeeks " ; vector < vector < int > > Q ; Q = { { 1 , 5 , 3 } , { 5 , 7 , 0 } , { 8 , 11 , 3 } , { 3 , 10 , 5 } , { 0 , 9 , 5 } } ; canMakePaliQueries ( str , Q ) ; return 0 ; }