README_EN.md

1915. Number of Wonderful Substrings

中文文档

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

Python3

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

Java

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

JavaScript

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

C++

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

Go

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

...