LeetCode 1915. Number of Wonderful Substrings Solution in Java, C++, Python & More | Explanation + Code

Description

A wonderful string is a string where at most one letter appears an odd number of times.

<li>For example, <code>&quot;ccjjc&quot;</code> and <code>&quot;abab&quot;</code> are wonderful, but <code>&quot;ab&quot;</code> is not.</li>

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: word = "aba"

Output: 4

Explanation: The four wonderful substrings are underlined below:

- "aba" -> "a"

- "aba" -> "b"

- "aba" -> "a"

- "aba" -> "aba"

Example 2:

Input: word = "aabb"

Output: 9

Explanation: The nine wonderful substrings are underlined below:

- "aabb" -> "a"

- "aabb" -> "aa"

- "aabb" -> "aab"

- "aabb" -> "aabb"

- "aabb" -> "a"

- "aabb" -> "abb"

- "aabb" -> "b"

- "aabb" -> "bb"

- "aabb" -> "b"

Example 3:

Input: word = "he"

Output: 2

Explanation: The two wonderful substrings are underlined below:

- "he" -> "h"

- "he" -> "e"

 

Constraints:

<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>

<li><code>word</code> consists of lowercase English letters from <code>&#39;a&#39;</code>&nbsp;to <code>&#39;j&#39;</code>.</li>

Solutions

Solution 1

PythonJavaC++GoTypeScriptJavaScript

class Solution: def wonderfulSubstrings(self, word: str) -> int: cnt = Counter({0: 1}) ans = st = 0 for c in word: st ^= 1 << (ord(c) - ord("a")) ans += cnt[st] for i in range(10): ans += cnt[st ^ (1 << i)] cnt[st] += 1 return ans(code-box)

class Solution { public long wonderfulSubstrings(String word) { int[] cnt = new int[1 << 10]; cnt[0] = 1; long ans = 0; int st = 0; for (char c : word.toCharArray()) { st ^= 1 << (c - 'a'); ans += cnt[st]; for (int i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } ++cnt[st]; } return ans; } }(code-box)

class Solution { public: long long wonderfulSubstrings(string word) { int cnt[1024] = {1}; long long ans = 0; int st = 0; for (char c : word) { st ^= 1 << (c - 'a'); ans += cnt[st]; for (int i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } ++cnt[st]; } return ans; } };(code-box)

func wonderfulSubstrings(word string) (ans int64) { cnt := [1024]int{1} st := 0 for _, c := range word { st ^= 1 << (c - 'a') ans += int64(cnt[st]) for i := 0; i < 10; i++ { ans += int64(cnt[st^(1<<i)]) } cnt[st]++ } return }(code-box)

function wonderfulSubstrings(word: string): number { const cnt: number[] = new Array(1 << 10).fill(0); cnt[0] = 1; let ans = 0; let st = 0; for (const c of word) { st ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)); ans += cnt[st]; for (let i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } cnt[st]++; } return ans; }(code-box)

/** * @param {string} word * @return {number} */ var wonderfulSubstrings = function (word) { const cnt = new Array(1024).fill(0); cnt[0] = 1; let ans = 0; let st = 0; for (const c of word) { st ^= 1 << (c.charCodeAt() - 'a'.charCodeAt()); ans += cnt[st]; for (let i = 0; i < 10; ++i) { ans += cnt[st ^ (1 << i)]; } cnt[st]++; } return ans; };(code-box)