Count of substrings with the frequency of at most one character as Odd - Coding

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 i^th character is represented by 2ⁱ. 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 i^th 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 j^th set-bit in the current mask and increment the value of the cnt by the frequency of bitmask after flipping the j^th 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:

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

Reffered: https://www.geeksforgeeks.org

Strings

Related
Sort the string as per ASCII values of the characters
Count subsequences 01 in string generated by concatenation of given numeric string K times
Make Palindrome binary string with exactly a 0s and b 1s by replacing wild card ?
Count of substrings from given Ternary strings containing characters at least once
Lexicographically smallest numeric string having odd digit counts

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13