Given a string S of length N containing only lowercase alphabets, the task is to print the count of substrings of the given string whose anagram is palindromic.
Examples:
Input: S = “aaaa”
Output: 10
Explanation:
Possible substrings are {“a”, “a”, “a”, “a”, “aa”, “aa”, “aa”, “aaa”, “aaa”, “aaaa”}. Since all substrings are have palindromic anagrams, the required answer is 10.Input: S = “abc”
Output: 3
Naive Approach: The idea is to generate all substrings of the given string and for each substring, check whether its anagram is a palindrome or not. Keep increasing the count of substrings for which the above condition is found to be true. Finally, print the count of all such substrings.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Bit Masking Approach: The idea is to generate the masks of 26-bit numbers as there are 26 characters. Also, observe that if the anagram of some string is a palindrome, then the frequencies of its characters except at most one character must be even.
Follow the steps below to solve the problem:
- Traverse the string and initialize a variable X = 0 at each index.
- From every ithe index, traverse the string over a range of indices [i, N – 1], and for each character S[j], calculate Bitwise XOR of X and 2(S[j] – ‘a’), where 0th bit represents if the frequency of a is odd, 1st bit represents if the frequency of b is odd, and so on.
- Then, check if X & (X – 1) is equal to 0 or not. If found to be true, then increment the count by 1.
Illustration:
Suppose, X = (0001000)2
=> (X – 1) will be represented as (0000111)2.
Therefore, X & (X – 1) = 0
- Once the above steps are exhausted, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print count of substrings// whose anagrams are palindromicvoid countSubstring(string s){ // Stores the answer int res = 0; // Iterate over the string for (int i = 0; i < s.length(); i++) { int x = 0; for (int j = i; j < s.length(); j++) { // Set the current character int temp = 1 << s[j] - 'a'; // Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } // Print the final count cout << res;}// Driver Codeint main(){ string str = "aaa"; // Function Call countSubstring(str); return 0;} |
Java
// Java program for // the above approachclass GFG{// Function to print count of subStrings// whose anagrams are palindromicstatic void countSubString(String s){ // Stores the answer int res = 0; // Iterate over the String for (int i = 0; i < s.length(); i++) { int x = 0; for (int j = i; j < s.length(); j++) { // Set the current character int temp = 1 << s.charAt(j) - 'a'; // Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } // Print the final count System.out.print(res);}// Driver Codepublic static void main(String[] args){ String str = "aaa"; // Function Call countSubString(str);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for# the above approach# Function to print count of subStrings# whose anagrams are palindromicdef countSubString(s): # Stores the answer res = 0; # Iterate over the String for i in range(len(s)): x = 0; for j in range(i, len(s)): # Set the current character temp = 1 << ord(s[j]) - ord('a'); # Parity update x ^= temp; if ((x & (x - 1)) == 0): res += 1; # Print final count print(res);# Driver Codeif __name__ == '__main__': str = "aaa"; # Function Call countSubString(str);# This code is contributed by 29AjayKumar |
C#
// C# program for // the above approachusing System;class GFG{// Function to print count of subStrings// whose anagrams are palindromicstatic void countSubString(String s){ // Stores the answer int res = 0; // Iterate over the String for (int i = 0; i < s.Length; i++) { int x = 0; for (int j = i; j < s.Length; j++) { // Set the current character int temp = 1 << s[j] - 'a'; // Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } // Print the readonly count Console.Write(res);}// Driver Codepublic static void Main(String[] args){ String str = "aaa"; // Function Call countSubString(str);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for//the above approach// Function to print count of subStrings// whose anagrams are palindromicfunction countSubString(s){ // Stores the answer let res = 0; // Iterate over the String for (let i = 0; i < s.length; i++) { let x = 0; for (let j = i; j < s.length; j++) { // Set the current character let temp = 1 << s[j] - 'a'; // Parity update x ^= temp; if ((x & (x - 1)) == 0) res++; } } // Print the final count document.write(res);} // Driver Code let str = "aaa"; // Function Call countSubString(str); // This code is contributed by souravghosh0416.</script> |
Output
6
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above Bit Masking technique, the idea is to use a Map. Follow the steps below to solve the problem:
- Initialize a map to store the frequencies of the masks. Initialize a variable X = 0.
- Traverse the string and for every ith index, calculate Bitwise XOR of X and 2(S[j] – ‘a’) and update the answer by adding the frequency of the current value of X in the Map because if any substring from 0 to j has the same mask as that of X, which is a mask for substring from 0 to i, then substring S[j + 1, i] will have even frequencies, where j < i.
- Also add the frequencies of masks X xor 2k, where, 0 ? k < 26. After that, increment the frequency of X by 1.
- Repeat the above steps for each index of the given string.
- After traversing the given string, print the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to get the count of substrings// whose anagrams are palindromicvoid countSubstring(string s){ // Store the answer int answer = 0; // Map to store the freq of masks unordered_map<int, int> m; // Set frequency for mask // 00...00 to 1 m[0] = 1; // Store mask in x from 0 to i int x = 0; for (int j = 0; j < s.length(); j++) { x ^= 1 << (s[j] - 'a'); // Update answer answer += m[x]; for (int i = 0; i < 26; ++i) { answer += m[x ^ (1 << i)]; } // Update frequency m[x] += 1; } // Print the answer cout << answer;}// Driver Codeint main(){ string str = "abab"; // Function Call countSubstring(str); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG {// Function to get the count of subStrings// whose anagrams are palindromicstatic void countSubString(String s) { // Store the answer int answer = 0; // Map to store the freq of masks HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Set frequency for mask // 00...00 to 1 m.put(0, 1); // Store mask in x from 0 to i int x = 0; for (int j = 0; j < s.length(); j++) { x ^= 1 << (s.charAt(j) - 'a'); // Update answer answer += m.containsKey(x) ? m.get(x) : 0; for (int i = 0; i < 26; ++i) { answer += m.containsKey(x ^ (1 << i)) ? m.get(x ^ (1 << i)) : 0; } // Update frequency if (m.containsKey(x)) m.put(x, m.get(x) + 1); else m.put(x, 1); } // Print the answer System.out.print(answer);}// Driver Codepublic static void main(String[] args) { String str = "abab"; // Function Call countSubString(str);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach from collections import defaultdict# Function to get the count of substrings# whose anagrams are palindromicdef countSubstring(s): # Store the answer answer = 0 # Map to store the freq of masks m = defaultdict(lambda : 0) # Set frequency for mask # 00...00 to 1 m[0] = 1 # Store mask in x from 0 to i x = 0 for j in range(len(s)): x ^= 1 << (ord(s[j]) - ord('a')) # Update answer answer += m[x] for i in range(26): answer += m[x ^ (1 << i)] # Update frequency m[x] += 1 # Print the answer print(answer)# Driver Codestr = "abab"# Function callcountSubstring(str)# This code is contributed by Shivam Singh |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{// Function to get the count of // subStrings whose anagrams // are palindromicstatic void countSubString(String s) { // Store the answer int answer = 0; // Map to store the freq of masks Dictionary<int, int> m = new Dictionary<int, int>(); // Set frequency for mask // 00...00 to 1 m.Add(0, 1); // Store mask in x from 0 to i int x = 0; for (int j = 0; j < s.Length; j++) { x ^= 1 << (s[j] - 'a'); // Update answer answer += m.ContainsKey(x) ? m[x] : 0; for (int i = 0; i < 26; ++i) { answer += m.ContainsKey(x ^ (1 << i)) ? m[x ^ (1 << i)] : 0; } // Update frequency if (m.ContainsKey(x)) m[x] = m[x] + 1; else m.Add(x, 1); } // Print the answer Console.Write(answer);}// Driver Codepublic static void Main(String[] args) { String str = "abab"; // Function Call countSubString(str);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function to get the count of substrings// whose anagrams are palindromicfunction countSubstring(s){ // Store the answer var answer = 0; // Map to store the freq of masks var m = new Map(); // Set frequency for mask // 00...00 to 1 m.set(0, 1); // Store mask in x from 0 to i var x = 0; for (var j = 0; j < s.length; j++) { x ^= 1 << (s[j].charCodeAt(0) - 'a'.charCodeAt(0)); // Update answer answer += m.has(x)? m.get(x):0; for (var i = 0; i < 26; ++i) { answer += m.has(x ^ (1 << i))?m.get(x ^ (1 << i)):0; } // Update frequency if(m.has(x)) m.set(x, m.get(x)+1) else m.set(x, 1) } // Print the answer document.write( answer);}// Driver Codevar str = "abab";// Function CallcountSubstring(str);</script> |
Output
7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
