Skip to content

1915. Number of Wonderful Substrings

Description

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

  • For example, "ccjjc" and "abab" are wonderful, but "ab" is not.

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:

  • 1 <= word.length <= 105
  • word consists of lowercase English letters from 'a'Β to 'j'.

Solutions

Solution 1: Prefix XOR + Counting

Since the string contains only \(10\) lowercase letters, we can use a \(10\)-bit integer to represent the parity of each letter count in the current prefix. The \(i\)-th bit is \(1\) if the \(i\)-th letter appears an odd number of times, and \(0\) if it appears an even number of times.

We iterate through each character in the string. Use a variable \(st\) to maintain the current prefix XOR state, and an array \(cnt\) to record how many times each prefix state has appeared. Initially, \(st = 0\) and \(cnt[0] = 1\).

For each character, update the prefix XOR state. If the current state has appeared \(cnt[st]\) times, it means there are \(cnt[st]\) substrings in which all letter counts are even, so we add \(cnt[st]\) to the answer. In addition, for \(0 \le i < 10\), toggling the \(i\)-th bit of \(st\) (i.e., \(st \oplus (1 << i)\)) represents substrings where exactly one letter has an odd count, so we add \(cnt[st \oplus (1 << i)]\) to the answer. Finally, increment the occurrence count of \(st\) by \(1\), and continue.

The time complexity is \(O(n \times \Sigma)\), and the space complexity is \(O(2^{\Sigma})\), where \(\Sigma = 10\) and \(n\) is the length of the string.

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        ans = st = 0
        for c in word:
            st ^= 1 << (ord(c) - ord("a"))
            ans += cnt[st]
            ans += sum(cnt[st ^ (1 << i)] for i in range(10))
            cnt[st] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn wonderful_substrings(word: String) -> i64 {
        let mut cnt = [0i64; 1 << 10];
        cnt[0] = 1;
        let mut ans: i64 = 0;
        let mut st: usize = 0;
        for c in word.chars() {
            st ^= 1 << (c as usize - 'a' as usize);
            ans += cnt[st];
            for i in 0..10 {
                ans += cnt[st ^ (1 << i)];
            }
            cnt[st] += 1;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @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;
};

Comments