map with {0: 1} to account for single character substrings and to handle cases where the bitmask does not change.

Count Substrings:

Traverse the string and update the bitmask for each character.
Check how many previous states of the bitmask (from the prefix map) can form a valid wonderful substring. This includes the current bitmask being exactly the same as a previous one or differs by a single bit (to allow one odd character).

Valid Masks:

We check if the current bitmask matches any of the previous occurrences.
We also check by toggling each bit to allow at most one character to have an odd count.

Code

[{"language":"Java","code":"class Solution {\n     public long wonderfulSubstrings(String word) {\n         long ans = 0;\n         HashMap<Integer, Integer> prefix = new HashMap<>();\n         int currentMask = 0;\n         prefix.put(0, 1);\n \n         for (char ch : word.toCharArray()) {\n             currentMask ^= 1 << (ch - 'a');\n \n             if (prefix.containsKey(currentMask)) {\n                 ans += prefix.get(currentMask);\n             }\n \n             for (int i = 0; i < 10; i++) {\n                 int targetMask = currentMask ^ (1 << i);\n                 ans += prefix.getOrDefault(targetMask, 0);\n             }\n             \n             prefix.put(currentMask, prefix.getOrDefault(currentMask, 0) + 1);\n         }\n         \n         return ans;\n     }\n }","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">     public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> wonderfulSubstrings</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(String </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">word</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">         long</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">         HashMap&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Integer</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Integer</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> prefix </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> new</span>

Related Tags