Check if a substring can be Palindromic by replacing K characters for Q queries | 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 ; Given a String str ; Given Queries ; Function call
function canMakePaliQueries ( str , Q ) { let n = str . length ; let dp = new Array ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = 0 ; } for ( let i = 0 ; i < 26 ; i ++ ) { let currentChar = String . fromCharCode ( i + ' ' . charCodeAt ( 0 ) ) ; for ( let j = 0 ; j < n ; j ++ ) { if ( j == 0 ) { dp [ i ] [ j ] = ( str [ j ] == currentChar ) ? 1 : 0 ; } else { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + ( ( str [ j ] == currentChar ) ? 1 : 0 ) ; } } } for ( let query of Q . values ( ) ) { let left = query [ 0 ] ; let right = query [ 1 ] ; let k = query [ 2 ] ; let unMatchedCount = 0 ; for ( let i = 0 ; i < 26 ; i ++ ) { let occurrence = dp [ i ] [ right ] - dp [ i ] [ left ] + ( str [ left ] == ( i + ' ' . charCodeAt ( 0 ) ) ? 1 : 0 ) ; if ( occurrence % 2 == 1 ) unMatchedCount ++ ; } let ans = unMatchedCount / 2 ; if ( ans <= k ) { document . write ( " " ) ; } else { document . write ( " " ) ; } } } let str = " " ; let Q = [ [ 1 , 5 , 3 ] , [ 5 , 7 , 0 ] , [ 8 , 11 , 3 ] , [ 3 , 10 , 5 ] , [ 0 , 9 , 5 ] ] ; canMakePaliQueries ( str , Q ) ;