Count of substrings with the frequency of at most one character as Odd
Given a string S of N characters, the task is to calculate the total number of non-empty substrings such that at most one character occurs an odd number of times.
Example:
Input: S = “aba”
Output: 4
Explanation: The valid substrings are “a”, “b”, “a”, and “aba”. Therefore, the total number of required substrings are 4.Input: “aabb”
Output: 9
Explanation: The valid substrings are “a”, “aa”, “aab”, “aabb”, “a”, “abb”, “b”, “bb”, and “b”.
Approach: The above problem can be solved with the help of Bit Masking using HashMaps. Follow the below-mentioned steps to solve the problem:
- The parity of the frequency of each character can be stored in a bitmask mask, where the ith character is represented by 2i. Initially the value of mask = 0.
- Create an unordered map seen, which stores the frequency of occurrence of each bitmask. Initially, the value of seen[0] = 1.
- Create a variable cnt, which stores the count of the valid substrings. Initially, the value of cnt = 0.
- Iterate for each i in the range [0, N) and Bitwise XOR the value of the mask with the integer representing the ith character of the string and increment the value of cnt by seen[mask].
- For each valid i, Iterate through all characters in the range [a, z] and increase its frequency by flipping the jth set-bit in the current mask and increment the value of the cnt by the frequency of bitmask after flipping the jth set-bit.
- The value stored in cnt is 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 find the count of substrings // such that at most one character occurs // odd number of times int uniqueSubstrings(string S) { // Stores the frequency of the bitmasks unordered_map< int , int > seen; // Initial Condition seen[0] = 1; // Store the current value of the bitmask int mask = 0; // Stores the total count of the // valid substrings int cnt = 0; for ( int i = 0; i < S.length(); ++i) { // XOR the mask with current character mask ^= (1 << (S[i] - 'a' )); // Increment the count by mask count // of strings with all even frequencies cnt += seen[mask]; for ( int j = 0; j < 26; ++j) { // Increment count by mask count // of strings if exist with the // jth character having odd frequency cnt += seen[mask ^ (1 << j)]; } seen[mask]++; } // Return Answer return cnt; } // Driver Code int main() { string word = "aabb" ; cout << uniqueSubstrings(word); return 0; } |
Java
import java.util.*; public class UniqueSubstrings { // Function to find the count of substrings // such that at most one character occurs // odd number of times public static int uniqueSubstrings(String S) { // Stores the frequency of the bitmasks HashMap<Integer, Integer> seen = new HashMap<>(); // Initial Condition seen.put( 0 , 1 ); // Store the current value of the bitmask int mask = 0 ; // Stores the total count of the // valid substrings int cnt = 0 ; for ( int i = 0 ; i < S.length(); ++i) { // XOR the mask with current character mask ^= ( 1 << (S.charAt(i) - 'a' )); // Increment the count by mask count // of strings with all even frequencies if (seen.containsKey(mask)) { cnt += seen.get(mask); } for ( int j = 0 ; j < 26 ; ++j) { // Increment count by mask count // of strings if exist with the // jth character having odd frequency if (seen.containsKey(mask ^ ( 1 << j))) { cnt += seen.get(mask ^ ( 1 << j)); } } seen.put(mask, seen.getOrDefault(mask, 0 ) + 1 ); } // Return Answer return cnt; } // Driver Code public static void main(String[] args) { String word = "aabb" ; System.out.println(uniqueSubstrings(word)); } } |
Python3
# Python program for the above approach # Function to find the count of substrings # such that at most one character occurs # odd number of times def uniqueSubstrings(S): # Stores the frequency of the bitmasks seen = {} # Initial Condition seen[ 0 ] = 1 # Store the current value of the bitmask mask = 0 # Stores the total count of the # valid substrings cnt = 0 for i in range ( len (S)): # XOR the mask with current character mask ^ = ( 1 << ( ord (S[i]) - ord ( 'a' ))) # Increment the count by mask count # of strings with all even frequencies if mask in seen: cnt + = seen[mask] else : cnt + = 0 for j in range ( 26 ): # Increment count by mask count # of strings if exist with the # jth character having odd frequency if mask ^ ( 1 << j) in seen: cnt + = seen[mask ^ ( 1 << j)] else : cnt + = 0 if mask in seen: seen[mask] + = 1 else : seen[mask] = 1 # Return Answer return cnt # Driver Code word = "aabb" print (uniqueSubstrings(word)) # This code is contributed by rj13to. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the count of substrings // such that at most one character occurs // odd number of times static int uniqueSubstrings( string S) { // Stores the frequency of the bitmasks Dictionary< int , int > seen = new Dictionary< int , int >(); // Initial Condition seen[0] = 1; // Store the current value of the bitmask int mask = 0; // Stores the total count of the // valid substrings int cnt = 0; for ( int i = 0; i < S.Length; ++i) { // XOR the mask with current character mask ^= (1 << (S[i] - 'a' )); // Increment the count by mask count // of strings with all even frequencies if (seen.ContainsKey(mask)) cnt += seen[mask]; for ( int j = 0; j < 26; ++j) { // Increment count by mask count // of strings if exist with the // jth character having odd frequency if (seen.ContainsKey(mask ^ (1 << j))) cnt += seen[mask ^ (1 << j)]; } if (seen.ContainsKey(mask)) seen[mask]++; else seen[mask] = 1; } // Return Answer return cnt; } // Driver Code public static void Main() { string word = "aabb" ; Console.WriteLine(uniqueSubstrings(word)); } } // This code is contributed by ukasp |
Javascript
// Javascript program for the above approach // Function to find the count of substrings // such that at most one character occurs // odd number of times function uniqueSubstrings(S) { // Stores the frequency of the bitmasks let seen = new Map(); // Initial Condition seen.set(0, 1); // Store the current value of the bitmask let mask = 0; // Stores the total count of the // valid substrings let cnt = 0; for (let i = 0; i < S.length; ++i) { // XOR the mask with current character mask ^= (1 << (S[i].charCodeAt(0) - 'a' .charCodeAt(0))); // Increment the count by mask count // of strings with all even frequencies if (seen.has(mask)) cnt += seen.get(mask); for (let j = 0; j < 26; ++j) { // Increment count by mask count // of strings if exist with the // jth character having odd frequency if (seen.has(mask ^ (1 << j))) cnt += seen.get(mask ^ (1 << j)); } if (seen.has(mask)) seen.set(mask, seen.get(mask) + 1); else seen.set(mask, 1); } // Return Answer return cnt; } // Driver Code let word = "aabb" ; document.write(uniqueSubstrings(word)); // This code is contributed by Saurabh Jaiswal |
Output:
9
Time Complexity: O(N*K)
Auxiliary Space: O(N)
Contact Us