Skip to content

1915. Number of Wonderful Substrings

SourceWeekly Contest 247 Q3DifficultyMediumRating2234

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

Thinking

Counting odd frequencies for every substring is \(O(n^2\cdot\Sigma)\) and fails for \(n\le 10^5\).

Ten letters fit in a 10-bit parity mask. Equal prefix xors give an even-count interval; xor differing by one bit gives exactly one odd letter.

At each position we add the historical prefixes whose mask equals the current one or differs by one bit, then record the current mask.

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