Count of substrings with the frequency of at most one character as Odd
source link: https://www.geeksforgeeks.org/count-of-substrings-with-the-frequency-of-at-most-one-character-as-odd/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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, wherethe 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:
- Python3
- Javascript
// 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 timesint uniqueSubstrings(string S){// Stores the frequency of the bitmasksunordered_map<int, int> seen;// Initial Conditionseen[0] = 1;// Store the current value of the bitmaskint mask = 0;// Stores the total count of the// valid substringsint cnt = 0;for (int i = 0; i < S.length(); ++i) {// XOR the mask with current charactermask ^= (1 << (S[i] - 'a'));// Increment the count by mask count// of strings with all even frequenciescnt += seen[mask];for (int j = 0; j < 26; ++j) {// Increment count by mask count// of strings if exist with the// jth character having odd frequencycnt += seen[mask ^ (1 << j)];}seen[mask]++;}// Return Answerreturn cnt;}// Driver Codeint main(){string word = "aabb";cout << uniqueSubstrings(word);return 0;} |
9
Time Complexity: O(N*K)
Auxiliary Space: O(N)
"The DSA course helped me a lot in clearing the interview rounds. It was really very helpful in setting a strong foundation for my problem-solving skills. Really a great investment, the passion Sandeep sir has towards DSA/teaching is what made the huge difference." - Gaurav | Placed at Amazon
Before you move on to the world of development, master the fundamentals of DSA on which every advanced algorithm is built upon. Choose your preferred language and start learning today:
DSA In JAVA/C++
DSA In Python
DSA In JavaScript
Trusted by Millions, Taught by One- Join the best DSA Course Today!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK