Number of wonderful substrings

Hash Table String Bit Manipulation Prefix Sum

66.6% acceptance

Feb 25, 2026

1829

284

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn wonderful_substrings(word: String) -> i64 {
    let mut count = vec![0i64; 1024]; // 2^10 bitmask states
    count[0] = 1;
    let mut mask = 0usize;
    let mut result = 0i64;
    for b in word.bytes() {
      mask ^= 1 << (b - b'a');
      // All even frequencies: same mask seen before
      result += count[mask];
      // Exactly one odd frequency: flip one bit
      for i in 0..10 {
        result += count[mask ^ (1 << i)];
      }
      count[mask] += 1;
    }
    result
  }
}