# LeetCode 1915. Number of Wonderful Substrings

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

## 題目大意

定義一個 **wonderful string** 為其至多一個組成的字母出現奇數次

給定一個字串 `word` 只由 `a` - `j` 合計 `10` 種小寫字母組成
回傳他有幾種這樣的 **wonderful substring** ？重複的分別計算

## 思考

這題輸入只由 `10` 種小寫字母組成，那我們其實可以直接用一個 $2^{10}$ 大小的陣列記錄
畢竟頻率狀態只有奇偶次兩種

class Solution
{
public:
    long long wonderfulSubstrings(string word)
    {
        long long ans = 0;
        int prefix = 0;
        array<int, 1024> cnt{};
        cnt[0] = 1;

        for (const char c : word)
        {
            prefix ^= 1 << (c - 'a');
            ans += cnt[prefix];

            for (int i = 0; i < 10; ++i)
            {
                ans += cnt[prefix ^ 1 << i];
            }

            ++cnt[prefix];
        }

        return ans;
    }
};

我們從左到右遍歷 `word` ，並且不斷 flip `prefix` 的特定位 (`c - 'a'`)

`prefix` 只會表達 `word[0:i]` 的情況 (`i` 表示某當前位置)，我們還要固定右邊的 `i` 再從左邊看有哪些符合的
這時後我們有記錄 `prefix` 就省去了重複遍歷的功夫

我們那個每次 `10` 遍的迴圈是跑過 `a` 到 `j` ，把當前 `prefix` 這 10 個位 flip 過來

並別忘了把現在的狀態最後頻率 `+1`