Check if a substring can be Palindromic by replacing K characters for Q queries | Java 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
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 . charAt ( j ) == currentChar ) ? 1 : 0 ; } else { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + ( ( str . charAt ( j ) == currentChar ) ? 1 : 0 ) ; } } } for ( int [ ] 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 . charAt ( left ) == ( i + ' a ' ) ? 1 : 0 ) ; if ( occurrence % 2 == 1 ) unMatchedCount ++ ; } int ans = unMatchedCount / 2 ; if ( ans <= k ) { System . out . print ( "YESNEW_LINE"); } else { System . out . print ( "NONEW_LINE"); } } } 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 ) ; } }