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 a String str ; Given Queries ; Function call
using System ; class GFG { static void canMakePaliQueries ( String str , int [ , ] Q ) { int n = str . Length ; int [ , ] dp = new int [ 26 , n ] ; for ( int i = 0 ; i < 26 ; i ++ ) { char currentChar = ( char ) ( i + ' a ' ) ; for ( int 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 ( int l = 0 ; l < Q . GetLength ( 0 ) ; l ++ ) { int [ ] query = GetRow ( Q , l ) ; 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 ' ) ? 1 : 0 ) ; if ( occurrence % 2 == 1 ) unMatchedCount ++ ; } int ans = unMatchedCount / 2 ; if ( ans <= k ) { Console . Write ( " YES STRNEWLINE " ) ; } else { Console . Write ( " NO STRNEWLINE " ) ; } } } public static int [ ] GetRow ( int [ , ] matrix , int row ) { var rowLength = matrix . GetLength ( 1 ) ; var rowVector = new int [ rowLength ] ; for ( var i = 0 ; i < rowLength ; i ++ ) rowVector [ i ] = matrix [ row , i ] ; return rowVector ; } public static void Main ( String [ ] args ) { String str = " GeeksforGeeks " ; int [ , ] Q = { { 1 , 5 , 3 } , { 5 , 7 , 0 } , { 8 , 11 , 3 } , { 3 , 10 , 5 } , { 0 , 9 , 5 } } ; canMakePaliQueries ( str , Q ) ; } }