# 1915. Number of Wonderful Substrings

• Time: $O(10n) = O(n)$
• Space: $O(1024) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: long long wonderfulSubstrings(string word) { long long ans = 0; int prefix = 0; // Binary prefix vector count(1024); // Binary prefix count count[0] = 1; // Empty string "" for (const char c : word) { prefix ^= 1 << c - 'a'; ans += count[prefix]; // All chars occur even times for (int i = 0; i < 10; ++i) // ('a' + i) occurs odd times ans += count[prefix ^ 1 << i]; ++count[prefix]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public long wonderfulSubstrings(String word) { long ans = 0; int prefix = 0; // Binary prefix int[] count = new int[1024]; // Binary prefix count count[0] = 1; // Empty string "" for (final char c : word.toCharArray()) { prefix ^= 1 << c - 'a'; ans += count[prefix]; // All chars occur even times for (int i = 0; i < 10; ++i) // ('a' + i) occurs odd times ans += count[prefix ^ 1 << i]; ++count[prefix]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def wonderfulSubstrings(self, word: str) -> int: ans = 0 prefix = 0 # Binary prefix count = [0] * 1024 # Binary prefix count count[0] = 1 # Empty string "" for c in word: prefix ^= 1 << ord(c) - ord('a') ans += count[prefix] # All chars occur even times # c occurs odd times ans += sum(count[prefix ^ 1 << i] for i in range(10)) count[prefix] += 1 return ans