https://leetcode.com/problems/number-of-wonderful-substrings/ from Google

Thinking process:

Checking the constraints. Usually when we see the limit is 10^5, that’s because the algorithm is NlogN complexity so that when N = 10^5, the overall time is 10^6, which is still fine in Leetcode’s environment.

However, we can see another contraint saying word consists of lowercase English letters from 'a' to 'j'. The number of English letters from a to j is 10. If we mutiply the these two limits together 10^5 x 10 = 10^6, this happens to be our upper limit as well. Hence, I guess we don’t need to use NlogN algorithm, instead, we can use 10 x N algorithm.

With that, we can imagine that we need to iterate through all indexes and for every index we need to check 10 possibilities. Basically we want to answer: given a index i, how many substrings which ends at index i and has at most one letter appears an odd number of times.

If our question is: given a substring starting at i and ending at j, is it a wonderful string? Then we can think of using prefix sum. Basically we need to know the prefix sum of all English letters of string[:i-1], and the prefix sum of all English letters of string[:j]. Then, we just need to subtract them and we can know the number of letters in string[i:j]. This will result in a N^2 solution, so it doesn’t work, but we notice that we can use prefix sum to get the number of appearance in a substring.

The other thing we notice is that what we actually care is if the number of appearance is odd or not, not the number. This makes us only need to remember two states for each English letter: odd and even. Whenever there is a thing with only two states, we can use bitmap.

With all of above observations, we only need to use a bitmap to represent the state of each English letter at the current position. For example, at index i, if number of a in the string[:i] is odd, we put it a 1 at position 0 in our bitmap. If the number of c in the string[:i] is odd, we put a 1 at the position 2 in our bitmap and so on. Then, at this example, we get a bitmap of b'0000000101.

Having this, we can answer our original question. At any given index, we only need to figure out how many prefix strings we already have which has one bit or zero bit difference against our current bitmap and that’s the answer for substring ending at i.

Here is the code.

 1class Solution {
 2public:
 3    long long wonderfulSubstrings(string word) {
 4        int cur = 0;
 5        long long ans = 0;
 6        unordered_map<int, long long> bitmapCnt;
 7        bitmapCnt[0] = 1;
 8        for (auto c : word) {
 9            cur = cur ^ (1 << (c - 'a'));
10            ans += bitmapCnt[cur];
11            for (int i=0; i<10; i++) {
12                if (cur & 1<<i) {
13                    ans += bitmapCnt[cur ^ (1<<i)];
14                }
15                else {
16                    ans += bitmapCnt[cur | (1<<i)];
17                }
18            }
19            bitmapCnt[cur]++;
20        }
21        return ans;
22    }
23};