Count substrings of a given string whose anagram is a palindrome
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 palindromic 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 final count cout << res; } // Driver Code int main() { string str = "aaa" ; // Function Call countSubstring(str); return 0; } |
Java
// Java program for // the above approach class GFG{ // Function to print count of subStrings // whose anagrams are palindromic static 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 Code public 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 palindromic def 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 Code if __name__ = = '__main__' : str = "aaa" ; # Function Call countSubString( str ); # This code is contributed by 29AjayKumar |
C#
// C# program for // the above approach using System; class GFG{ // Function to print count of subStrings // whose anagrams are palindromic static 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 Code public 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 palindromic function 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> |
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 palindromic void 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 Code int main() { string str = "abab" ; // Function Call countSubstring(str); return 0; } |
Java
// Java program for // the above approach import java.util.*; class GFG { // Function to get the count of subStrings // whose anagrams are palindromic static 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 Code public 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 palindromic def 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 Code str = "abab" # Function call countSubstring( str ) # This code is contributed by Shivam Singh |
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to get the count of // subStrings whose anagrams // are palindromic static 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 Code public 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 palindromic function 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 Code var str = "abab" ; // Function Call countSubstring(str); </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(N)