number-of-wonderful-substrings

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A wonderful string is a string where at most one letter appears an odd number of times.

<ul>
	<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>
</ul>

Given a string <code>word</code> that consists of the first ten lowercase English letters (<code>&#39;a&#39;</code> through <code>&#39;j&#39;</code>), return the number of wonderful non-empty substrings in <code>word</code>. If the same substring appears multiple times in <code>word</code>, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

&nbsp;
Example 1:

<pre>
Input: word = &quot;aba&quot;
Output: 4
Explanation: The four wonderful substrings are underlined below:
- &quot;aba&quot; -&gt; &quot;a&quot;
- &quot;aba&quot; -&gt; &quot;b&quot;
- &quot;aba&quot; -&gt; &quot;a&quot;
- &quot;aba&quot; -&gt; &quot;aba&quot;
</pre>

Example 2:

<pre>
Input: word = &quot;aabb&quot;
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- &quot;aabb&quot; -&gt; &quot;a&quot;
- &quot;aabb&quot; -&gt; &quot;aa&quot;
- &quot;aabb&quot; -&gt; &quot;aab&quot;
- &quot;aabb&quot; -&gt; &quot;aabb&quot;
- &quot;aabb&quot; -&gt; &quot;a&quot;
- &quot;aabb&quot; -&gt; &quot;abb&quot;
- &quot;aabb&quot; -&gt; &quot;b&quot;
- &quot;aabb&quot; -&gt; &quot;bb&quot;
- &quot;aabb&quot; -&gt; &quot;b&quot;
</pre>

Example 3:

<pre>
Input: word = &quot;he&quot;
Output: 2
Explanation: The two wonderful substrings are underlined below:
- &quot;he&quot; -&gt; &quot;h&quot;
- &quot;he&quot; -&gt; &quot;e&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word.length &lt;= 105</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>
</ul>

wonderfulSubstrings

Number of Wonderful Substrings

Bit Manipulation

Hash Table

String

Prefix Sum

如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

<ul>
	<li>例如，<code>"ccjjc"</code> 和 <code>"abab"</code> 都是最美字符串，但 <code>"ab"</code> 不是。</li>
</ul>

给你一个字符串 <code>word</code> ，该字符串由前十个小写英文字母组成（<code>'a'</code> 到 <code>'j'</code>）。请你返回 <code>word</code> 中 最美非空子字符串 的数目。如果同样的子字符串在 <code>word</code> 中出现多次，那么应当对 每次出现 分别计数。

子字符串 是字符串中的一个连续字符序列。

 

示例 1：

<pre>
输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"
</pre>

示例 2：

<pre>
输入：word = "aabb"
输出：9
解释：9 个最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"
</pre>

示例 3：

<pre>
输入：word = "he"
输出：2
解释：2 个最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"
</pre>

 

提示：

<ul>
	<li><code>1 <= word.length <= 105</code></li>
	<li><code>word</code> 由从 <code>'a'</code> 到 <code>'j'</code> 的小写英文字母组成</li>
</ul>