Count of K | C ++ program for the above approach ; To store the frequency array ; Function to check palindromic of of any substring using frequency array ; Initialise the odd count ; Traversing frequency array to compute the count of characters having odd frequency ; Returns true if odd count is atmost 1 ; Function to count the total number substring whose any permutations are palindromic ; Computing the frequency of first K character of the string ; To store the count of palindromic permutations ; Checking for the current window if it has any palindromic permutation ; Start and end point of window ; Decrementing count of first element of the window ; Incrementing count of next element of the window ; Checking current window character frequency count ; Return the final count ; Driver Code ; Given string str ; Window of size K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > freq ( 26 ) ; bool checkPalindrome ( ) { int oddCnt = 0 ; for ( auto x : freq ) { if ( x % 2 == 1 ) oddCnt ++ ; } return oddCnt <= 1 ; } int countPalindromePermutation ( string s , int k ) { for ( int i = 0 ; i < k ; i ++ ) { freq [ s [ i ] - 97 ] ++ ; } int ans = 0 ; if ( checkPalindrome ( ) ) { ans ++ ; } int i = 0 , j = k ; while ( j < s . size ( ) ) { freq [ s [ i ++ ] - 97 ] -- ; freq [ s [ j ++ ] - 97 ] ++ ; if ( checkPalindrome ( ) ) { ans ++ ; } } return ans ; } int main ( ) { string str = " abbaca " ; int K = 3 ; cout << countPalindromePermutation ( str , K ) << endl ; return 0 ; }