# 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**:

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input: S = “aba”Output: 4Explanation: The valid substrings are “a”, “b”, “a”, and “aba”. Therefore, the total number of required substrings are 4.

Input: “aabb”Output: 9Explanation: 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**i**character is represented by^{th}**2**. Initially the value of^{i}**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**i**character of the string and increment the value of^{th}**cnt**by**seen[mask]**. - For each valid
**i**, Iterate through all characters in the range**[a, z]**and increase its frequency by flipping the**j**set-bit in the current mask and increment the value of the^{th}**cnt**by the frequency of bitmask after flipping the**j**set-bit.^{th} - 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; ` `}` |

**Output:**

9

**Time Complexity**: O(N)**Auxiliary Space**: O(N)