Prefix sum and bit manipulation

1915. Number of Wonderful Substrings

  1. all characters have an even number of occurrences.
  2. Only one character has an odd number occurrence: try from a to j.
/*
0,
a 1
aa 0
aaa 1
*/
typedef long long LL;
class Solution {
public:
int helper(int curr, unordered_map<int, int>& cnt, int j){
int prev_matched = curr ^ (1 << j);
return cnt[prev_matched];
}
long long wonderfulSubstrings(string word) {
const int n = word.size();
vector<int> cusum;
cusum.push_back(0);
for (int i = 0; i < n; ++i)
{
cusum.push_back(cusum.back() ^ (1 << (word[i] - 'a')));
}
LL ret = 0;
/*
0,
a 1
aa 0
aaa 1
*/
unordered_map<int, int> cnt;
cnt[0] = 1;
for (int i = 0; i < n; ++i)
{
// even for all
ret += cnt[cusum[i+1]];
// odd for a, b, c, ... j
for (int j = 0; j <= int('j' - 'a'); ++j){
auto thisret = helper(cusum[i + 1], cnt, j);
ret += (LL)thisret;
}
cnt[cusum[i + 1]] += 1;
}
return ret;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Find() vs. Filter() in JavaScript

Migrating from Gulp/Webpack configuration to Webpack-only configuration.

Javascript prototypal model and inheritance

How to use Generics with Arrow functions in TypeScript

Truthy and Falsy values, Null Vs Undefined, double equal (==) vs triple equal (===)

Quick Overview of Deno JavaScript Runtime

Laravel Advance | Delete record using ajax request in Laravel Example

Webpack 5 Module Federation — Stitching two simple bundles together

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Why should we study algorithms? — [Introduction to Algorithms]

Need for different sorting algorithms

What are the features of spring framework?

Creating a Binary Search Tree, inserting and LeetCode 653