# 30.04.2024 [1915. Number of Wonderful Substrings]
Count substrings with at most one odd frequency #medium #bit_manipulation
30.04.2024
1915. Number of Wonderful Substrings medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/588
Problem TLDR
Count substrings with at most one odd frequency #medium #bit_manipulation
Intuition
This is a hard problem.
Let’s try to look at the problem with our bare hands:
// aba
// a a
// ab -
// b b
// ba -
// aba aba
// aab
// a + xor = a
// aa + xor = 0
// a + xor = a
// aab + xor = b
// ab - xor = ab
// b + xor = b
// * = (aa, a) + b
// dp or two-pointers?
// dp: f(aabb) = f(aab)? + b
// two pointers:
// aabb
// i move i: a + a + b + b + aa + aab + aabb
// j move j: abb + bb
// skip ab?
We quickly run out of possible solutions patterns: neither dp or two pointers approach would work.
However, there are some thoughts:
only odd-even matters, so, we can somehow use
xor
xor
works well for intervali..j
when we pre-compute all the prefixes:xor i..j = xor 0..j xor 0..i
This is where my brain has stopped, and I used the hints:
use prefixes bitmask, as we only have
10
unique chars
Let’s try to make use of the prefix’s bitmasks:
// bitmask 00
// a 01
// a 00
// b 10 m[ab] = m[aab] xor m[a]
// b 00 m[abb] = m[aabb] xor m[a]
// how many previous masks have mismatched bits?
// ~~~~~~~~~~
We know the current prefix bitmask m
and our interest is how many subarrays on the left are good. We can xor with all the previous masks to find out the xor result of subarrays: this result must have at most one 1
bit. We can compress this search by putting unique masks in a counter HashMap.
// mismatched = differs 1 bit or equal
//
// ab m
// 00
// a 01 +1(00)
// b 11 +1(01)
// 0123
// aabb m res
// 00
//0a 01 +1(00)
//1 a 00 +2(00,01)
//2 b 10 +2(00,00)
//3 b 00 +4(00,01,00,10)
//
Approach
Another neat trick: we don’t have to check all the masks from a HashMap, just check by changing every
10
bits of mask.array is faster, we have at most
2^10
unique bits combinations
Complexity
Time complexity:
O(n)Space complexity:
O(2^k), k - is an alphabet, at most 2^10 masks total
Code
fun wonderfulSubstrings(word: String): Long {
val masksCounter = LongArray(1024); masksCounter[0] = 1
var m = 0; var res = 0L
for (c in word) {
m = m xor (1 shl (c.code - 'a'.code))
res += masksCounter[m]
for (i in 0..9) res += masksCounter[m xor (1 shl i)]
masksCounter[m]++
}
return res
}
pub fn wonderful_substrings(word: String) -> i64 {
let mut counter = vec![0; 1024]; counter[0] = 1;
let (mut m, mut res) = (0, 0);
for b in word.bytes() {
m ^= 1 << (b - b'a');
res += counter[m];
for i in 0..10 { res += counter[m ^ (1 << i)] }
counter[m] += 1
}; res
}