Given string str consists of only lowercase alphabets and an integer K, the task is to count the number of substrings of size K such that any permutation of the substring is a palindrome.
Examples:
Input: str = “abbaca”, K = 3
Output: 3
Explanation:
The substrings of size 3 whose permutation is palindrome are {“abb”, “bba”, “aca”}.Input: str = “aaaa”, K = 1
Output: 4
Explanation:
The substrings of size 1 whose permutation is palindrome are {‘a’, ‘a’, ‘a’, ‘a’}.
Naive Approach: A naive solution is to run a two-loop to generate all substrings of size K. For each substring formed, find the frequency of each character of the substring. If at most one character has an odd frequency, then one of its permutations will be a palindrome. Increment the count for the current substring and print the final count after all the operations.
Time Complexity: O(N*K)
Efficient Approach: This problem can be solved efficiently by using the Window Sliding Technique and using a frequency array of size 26. Below are the steps:
- Store the frequency of the first K elements of the given string in a frequency array(say freq[]).
- Using a frequency array, check the count of elements having an odd frequency. If it is less than 2, then the increment of the count of palindromic permutation.
- Now, linearly slide the window ahead till it reaches the end.
- At each iteration, decrease the count of the first element of the window by 1 and increase the count of the next element of the window by 1 and again check the count of elements in a frequency array having an odd frequency. If it is less than 2, then increase the count of the palindromic permutation.
- Repeat the above step till we reach the end of the string and print the count of palindromic permutation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// To store the frequency arrayvector<int> freq(26);// Function to check palindromic of// of any substring using frequency arraybool checkPalindrome(){ // Initialise the odd count int oddCnt = 0; // Traversing frequency array to // compute the count of characters // having odd frequency for (auto x : freq) { if (x % 2 == 1) oddCnt++; } // Returns true if odd count is atmost 1 return oddCnt <= 1;}// Function to count the total number// substring whose any permutations// are palindromicint countPalindromePermutation( string s, int k){ // Computing the frequency of // first K character of the string for (int i = 0; i < k; i++) { freq[s[i] - 97]++; } // To store the count of // palindromic permutations int ans = 0; // Checking for the current window // if it has any palindromic // permutation if (checkPalindrome()) { ans++; } // Start and end point of window int i = 0, j = k; while (j < s.size()) { // Sliding window by 1 // Decrementing count of first // element of the window freq[s[i++] - 97]--; // Incrementing count of next // element of the window freq[s[j++] - 97]++; // Checking current window // character frequency count if (checkPalindrome()) { ans++; } } // Return the final count return ans;}// Driver Codeint main(){ // Given string str string str = "abbaca"; // Window of size K int K = 3; // Function Call cout << countPalindromePermutation(str, K) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// To store the frequency arraystatic int []freq = new int[26];// Function to check palindromic of// of any subString using frequency arraystatic boolean checkPalindrome(){ // Initialise the odd count int oddCnt = 0; // Traversing frequency array to // compute the count of characters // having odd frequency for(int x : freq) { if (x % 2 == 1) oddCnt++; } // Returns true if odd count // is atmost 1 return oddCnt <= 1;}// Function to count the total number// subString whose any permutations// are palindromicstatic int countPalindromePermutation(char []s, int k){ // Computing the frequency of // first K character of the String for(int i = 0; i < k; i++) { freq[s[i] - 97]++; } // To store the count of // palindromic permutations int ans = 0; // Checking for the current window // if it has any palindromic // permutation if (checkPalindrome()) { ans++; } // Start and end point of window int i = 0, j = k; while (j < s.length) { // Sliding window by 1 // Decrementing count of first // element of the window freq[s[i++] - 97]--; // Incrementing count of next // element of the window freq[s[j++] - 97]++; // Checking current window // character frequency count if (checkPalindrome()) { ans++; } } // Return the final count return ans;}// Driver Codepublic static void main(String[] args){ // Given String str String str = "abbaca"; // Window of size K int K = 3; // Function Call System.out.print(countPalindromePermutation( str.toCharArray(), K) + "\n");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# To store the frequency array freq = [0] * 26# Function to check palindromic of # of any substring using frequency array def checkPalindrome(): # Initialise the odd count oddCnt = 0 # Traversing frequency array to # compute the count of characters # having odd frequency for x in freq: if (x % 2 == 1): oddCnt += 1 # Returns true if odd count is atmost 1 return oddCnt <= 1# Function to count the total number # substring whose any permutations # are palindromic def countPalindromePermutation(s, k): # Computing the frequency of # first K character of the string for i in range(k): freq[ord(s[i]) - 97] += 1 # To store the count of # palindromic permutations ans = 0 # Checking for the current window # if it has any palindromic # permutation if (checkPalindrome()): ans += 1 # Start and end point of window i = 0 j = k while (j < len(s)): # Sliding window by 1 # Decrementing count of first # element of the window freq[ord(s[i]) - 97] -= 1 i += 1 # Incrementing count of next # element of the window freq[ord(s[j]) - 97] += 1 j += 1 # Checking current window # character frequency count if (checkPalindrome()): ans += 1 # Return the final count return ans # Driver Code # Given string str str = "abbaca"# Window of size K K = 3# Function call print(countPalindromePermutation(str, K))# This code is contributed by code_hunt |
C#
// C# program for the above approachusing System;class GFG{// To store the frequency arraystatic int []freq = new int[26];// Function to check palindromic of// of any subString using frequency arraystatic bool checkPalindrome(){ // Initialise the odd count int oddCnt = 0; // Traversing frequency array to // compute the count of characters // having odd frequency foreach(int x in freq) { if (x % 2 == 1) oddCnt++; } // Returns true if odd count // is atmost 1 return oddCnt <= 1;}// Function to count the total number// subString whose any permutations// are palindromicstatic int countPalindromePermutation(char []s, int k){ int i = 0; // Computing the frequency of // first K character of the String for(i = 0; i < k; i++) { freq[s[i] - 97]++; } // To store the count of // palindromic permutations int ans = 0; // Checking for the current window // if it has any palindromic // permutation if (checkPalindrome()) { ans++; } // Start and end point of window int j = k; i = 0; while (j < s.Length) { // Sliding window by 1 // Decrementing count of first // element of the window freq[s[i++] - 97]--; // Incrementing count of next // element of the window freq[s[j++] - 97]++; // Checking current window // character frequency count if (checkPalindrome()) { ans++; } } // Return the final count return ans;}// Driver Codepublic static void Main(String[] args){ // Given String str String str = "abbaca"; // Window of size K int K = 3; // Function Call Console.Write(countPalindromePermutation( str.ToCharArray(), K) + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// To store the frequency arrayvar freq = Array(26).fill(0);// Function to check palindromic of// of any substring using frequency arrayfunction checkPalindrome(){ // Initialise the odd count var oddCnt = 0; // Traversing frequency array to // compute the count of characters // having odd frequency freq.forEach(x => { if (x % 2 == 1) oddCnt++; }); // Returns true if odd count is atmost 1 return oddCnt <= 1;}// Function to count the total number// substring whose any permutations// are palindromicfunction countPalindromePermutation( s, k){ // Computing the frequency of // first K character of the string for (var i = 0; i < k; i++) { freq[s[i].charCodeAt(0) - 97]++; } // To store the count of // palindromic permutations var ans = 0; // Checking for the current window // if it has any palindromic // permutation if (checkPalindrome()) { ans++; } // Start and end point of window var i = 0, j = k; while (j < s.length) { // Sliding window by 1 // Decrementing count of first // element of the window freq[s[i++].charCodeAt(0) - 97]--; // Incrementing count of next // element of the window freq[s[j++].charCodeAt(0) - 97]++; // Checking current window // character frequency count if (checkPalindrome()) { ans++; } } // Return the final count return ans;}// Driver Code// Given string strvar str = "abbaca";// Window of size Kvar K = 3;// Function Calldocument.write( countPalindromePermutation(str, K));</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Brute Force in python:
Approach:
In this approach, we will check all possible substrings of size K and count those substrings whose permutations are palindromic.
Algorithm:
Initialize a count variable to zero.
Loop through all substrings of size K.
For each substring, generate all possible permutations.
Check if any of the permutations is a palindrome.
If yes, then increment the count variable.
Return the count variable.
C++
#include <iostream>#include <vector>#include <algorithm>#include <set>// Helper function to generate permutations of a vector of characters.void generatePermutationsHelper(std::vector<char>& chars, std::set<std::vector<char>>& perms, int index) { // If the current index is at the end of the vector, insert the permutation into the set. if (index == chars.size() - 1) { perms.insert(chars); return; } // Generate permutations by swapping characters at the current index with characters // from the current index to the end of the vector. for (int i = index; i < chars.size(); i++) { std::swap(chars[index], chars[i]); generatePermutationsHelper(chars, perms, index + 1); std::swap(chars[index], chars[i]); // Restore the original order for the next iteration. }}// Function to generate all permutations of a vector of characters and store them in a set.void generatePermutations(std::vector<char>& chars, std::set<std::vector<char>>& perms) { generatePermutationsHelper(chars, perms, 0);}// Function to check if a vector of characters forms a palindrome.bool isPalindrome(const std::vector<char>& chars) { int left = 0; int right = chars.size() - 1; while (left < right) { if (chars[left] != chars[right]) { return false; } left++; right--; } return true;}// Function to count the number of palindromic substrings of length k in a given string.int countPalindromicSubstringsBrute(const std::string& s, int k) { int n = s.length(); int count = 0; for (int i = 0; i < n - k + 1; i++) { std::string substr = s.substr(i, k); std::vector<char> chars(substr.begin(), substr.end()); std::set<std::vector<char>> perms; generatePermutations(chars, perms); bool isPalindromic = false; for (const auto& perm : perms) { if (isPalindrome(perm)) { isPalindromic = true; break; } } if (isPalindromic) { count++; } } return count;}int main() { // Example 1: Count palindromic substrings of length 3 in the string "abbaca". std::string s1 = "abbaca"; int k1 = 3; std::cout << countPalindromicSubstringsBrute(s1, k1) << std::endl; // Output: 3 // Example 2: Count palindromic substrings of length 1 in the string "aaaa". std::string s2 = "aaaa"; int k2 = 1; std::cout << countPalindromicSubstringsBrute(s2, k2) << std::endl; // Output: 4 return 0;} |
Java
import java.util.*;public class Main { public static int countPalindromicSubstringsBrute(String s, int k) { int n = s.length(); int count = 0; for (int i = 0; i < n - k + 1; i++) { String substr = s.substring(i, i + k); List<Character> chars = new ArrayList<>(); for (char c : substr.toCharArray()) { chars.add(c); } Set<List<Character>> perms = new HashSet<>(); generatePermutations(chars, perms); boolean isPalindromic = false; for (List<Character> perm : perms) { if (isPalindrome(perm)) { isPalindromic = true; break; } } if (isPalindromic) { count++; } } return count; } public static void generatePermutations(List<Character> chars, Set<List<Character>> perms) { generatePermutationsHelper(chars, perms, 0); } public static void generatePermutationsHelper(List<Character> chars, Set<List<Character>> perms, int index) { if (index == chars.size() - 1) { perms.add(new ArrayList<>(chars)); } for (int i = index; i < chars.size(); i++) { Collections.swap(chars, index, i); generatePermutationsHelper(chars, perms, index + 1); Collections.swap(chars, index, i); } } public static boolean isPalindrome(List<Character> chars) { int left = 0; int right = chars.size() - 1; while (left < right) { if (!chars.get(left).equals(chars.get(right))) { return false; } left++; right--; } return true; } public static void main(String[] args) { String s1 = "abbaca"; int k1 = 3; System.out.println(countPalindromicSubstringsBrute(s1, k1)); // Output: 3 String s2 = "aaaa"; int k2 = 1; System.out.println(countPalindromicSubstringsBrute(s2, k2)); // Output: 4 }} |
Python3
import itertoolsdef count_palindromic_substrings_brute(s: str, k: int) -> int: n = len(s) count = 0 for i in range(n-k+1): substr = s[i:i+k] perms = itertools.permutations(substr) for perm in perms: if perm == perm[::-1]: count += 1 break return count# Example usage:s1 = "abbaca"k1 = 3print(count_palindromic_substrings_brute(s1, k1)) # Output: 3s2 = "aaaa"k2 = 1print(count_palindromic_substrings_brute(s2, k2)) # Output: 4 |
Output
3 4
Time Complexity: O(n^k * k!)
Space Complexity: O(k!)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!