Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Number of Wonderful Substrings solution and explanation

MediumBit ManipulationHash TablePrefix SumString5 min read66.8% acceptanceUpdated 9 Apr 2026
Asked atUberGoogle
Practise Number of Wonderful Substrings
38:20
Number of Wonderful Substrings | Clear Intuition | Full Dry Run | Leetcode 1915 | codestorywithMIKcodestorywithMIK · 38:20 · 15K viewsWatch on YouTube
9 more videos on this problem
  1. Number of Wonderful Substrings | Clear Intuition | Full Dry Run | Leetcode 1915 | codestorywithMIKcodestorywithMIK · 38:20 · 15K views
  2. LeetCode 1915. Number of Wonderful SubstringsHappy Coding · 18:01 · 12K views
  3. 1915. Number of Wonderful Substrings | Bit Manipulation | Bit Masking | XOR | De-shawAryan Mittal · 37:14 · 10K views
  4. 1915. Number of Wonderful Substrings (Leetcode Medium)Programming Live with Larry · 25:29 · 2K views
  5. Daily Leetcode #1491: Apr 30, 2024 - 1915. Number of Wonderful SubstringsProgramming Live with Larry · 23:12 · 1K views
  6. LeetCode 1915 - Number of Wonderful Substrings - JavaAlpha-Code · 28:33 · 429 views
  7. Number of Wonderful SubstringsDaily Leetcode · 9:06 · 362 views
  8. LeetCode Problem 1915: Number of Wonderful Substrings | CodeRebel.CodeRebel · 9:37 · 244 views
  9. 1915. Number of Wonderful SubstringsLeetcodeDaily · 1:26:20 · 168 views
  10. [April 30, 2024, LeetCode daily] 1915. Number of Wonderful Substrings - Python, solution explainedhornclause · 7:29 · 95 views

The problem

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'.

Approach overview

Problem Overview: Given a string consisting of the first ten lowercase letters (a–j), count how many substrings are wonderful. A substring is wonderful when at most one character appears an odd number of times. The task is essentially checking parity of character counts across all substrings efficiently.

Approach 1: Bitmask and Prefix Sum (O(n) time, O(1) space)

The key observation: you only care whether each character count is odd or even. That means you can represent the state of the string using a 10‑bit mask where bit i indicates whether character 'a' + i currently has odd frequency. As you iterate through the string, update this mask using XOR. Each mask represents the parity state of the prefix.

A substring is wonderful if its parity mask has either zero odd characters or exactly one odd character. Using the prefix sum idea, the parity of substring [l..r] equals prefixMask[r] ^ prefixMask[l-1]. To count valid substrings ending at position r, track how many times each mask has appeared using a hash table or array of size 2^10. First add matches where the mask is identical (all even counts). Then flip each of the 10 bits and check those masks to allow exactly one odd character. Each step performs constant work, giving O(n * 10) ≈ O(n) time and O(2^10) space.

This approach relies heavily on bit manipulation. The bitmask compresses parity information into a small integer, making state comparison extremely fast.

Approach 2: Sliding Window (Basic) (O(n^2) time, O(1) space)

A more straightforward idea expands substrings using a sliding window style enumeration. Fix the left boundary and extend the right pointer while tracking frequency counts for the ten characters. After each extension, compute how many characters currently have odd counts. If that number is ≤ 1, the substring is wonderful.

This method uses a small frequency array of size 10 and updates counts as the window expands. Checking the odd-count condition requires scanning the array or maintaining an auxiliary counter. While easy to implement, every starting index may scan many characters, resulting in O(n^2) time in the worst case. Space remains O(1) since the alphabet size is fixed.

Recommended for interviews: The bitmask + prefix frequency approach is what interviewers expect. It reduces the substring parity check to constant-time mask comparisons and demonstrates strong understanding of prefix techniques and parity encoding. The quadratic window approach is useful for reasoning about the problem initially, but the optimized bitmask solution shows the algorithmic insight required for medium-level string problems.

Approach 1: Approach 1: Bitmask and Prefix Sum

This approach uses bitmasking to track the odd/even status of character frequencies. We use a prefix sum technique to maintain these statuses as the string is iterated upon.

from collections import defaultdict

def wonderful_substrings(word):
    prefix_status = defaultdict(int)
    prefix_status[0] = 1
    curr_status, count = 0, 0

    for c in word:
        curr_status ^= (1 << (ord(c) - ord('a')))
        count += prefix_status[curr_status]
        for i in range(10):
            count += prefix_status[curr_status ^ (1 << i)]
        prefix_status[curr_status] += 1

    return count

print(wonderful_substrings("aba"))
import java.util.HashMap;

public class WonderfulSubstrings {
    public static int wonderfulSubstrings(String word) {
        HashMap<Integer, Integer> prefixStatus = new HashMap<>();
        prefixStatus.put(0, 1);
        int currStatus = 0, count = 0;

        for (char c : word.toCharArray()) {
            currStatus ^= (1 << (c - 'a'));
            count += prefixStatus.getOrDefault(currStatus, 0);
            for (int i = 0; i < 10; i++) {
                count += prefixStatus.getOrDefault(currStatus ^ (1 << i), 0);
            }
            prefixStatus.put(currStatus, prefixStatus.getOrDefault(currStatus, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(wonderfulSubstrings("aba"));
    }
}
#include <iostream>
#include <unordered_map>
using namespace std;

int wonderfulSubstrings(string word) {
    unordered_map<int, int> prefixStatus = {{0, 1}};
    int currStatus = 0, count = 0;

    for (char c : word) {
        currStatus ^= (1 << (c - 'a'));
        count += prefixStatus[currStatus];
        for (int i = 0; i < 10; i++) {
            count += prefixStatus[currStatus ^ (1 << i)];
        }
        prefixStatus[currStatus]++;
    }

    return count;
}

int main() {
    cout << wonderfulSubstrings("aba") << endl;
    return 0;
}
function wonderfulSubstrings(word) {
    const prefixStatus = {0: 1};
    let currStatus = 0, count = 0;

    for (const char of word) {
        currStatus ^= (1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)));
        count += prefixStatus[currStatus] || 0;
        for (let i = 0; i < 10; i++) {
            count += prefixStatus[currStatus ^ (1 << i)] || 0;
        }
        prefixStatus[currStatus] = (prefixStatus[currStatus] || 0) + 1;
    }

    return count;
}

console.log(wonderfulSubstrings("aba"));
#include <stdio.h>
#include <string.h>

int wonderfulSubstrings(char* word) {
    int prefixStatus[1024] = {1}; // 2^10 states initialized
    int currStatus = 0, count = 0;

    for (; *word != '\0'; word++) {
        currStatus ^= (1 << (*word - 'a'));
        count += prefixStatus[currStatus];
        for (int i = 0; i < 10; i++)
            count += prefixStatus[currStatus ^ (1 << i)];
        prefixStatus[currStatus]++;
    }

    return count;
}

int main() {
    char word[] = "aba";
    printf("%d\n", wonderfulSubstrings(word));
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public int WonderfulSubstrings(string word) {
        var prefixStatus = new Dictionary<int, int>();
        prefixStatus[0] = 1;
        int currStatus = 0, count = 0;

        foreach (char c in word) {
            currStatus ^= (1 << (c - 'a'));
            count += prefixStatus.ContainsKey(currStatus) ? prefixStatus[currStatus] : 0;
            for (int i = 0; i < 10; i++) {
                count += prefixStatus.ContainsKey(currStatus ^ (1 << i)) ? prefixStatus[currStatus ^ (1 << i)] : 0;
            }
            if (!prefixStatus.ContainsKey(currStatus)) {
                prefixStatus[currStatus] = 0;
            }
            prefixStatus[currStatus]++;
        }

        return count;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.WonderfulSubstrings("aba"));
    }
}

Python’s defaultdict is leveraged for prefix tracking. The iterative process through each character in the string checks the current character's bit-state, adjusts the `prefix_status`, and accumulates the count of wonderful substrings based on state proximity.

Complexity

Time Complexity: O(n * k),
Space Complexity: O(2^k).

Try this approach in the editor

Approach 2: Approach 2: Sliding Window (Basic)

This approach uses a non-optimized sliding window technique over the string to identify all substrings and individually verify their "wonderfulness" by counting character frequencies.

def is_wonderful(substr):
    freq = [0] * 10
    for c in substr:
        freq[ord(c) - ord('a')] += 1
    return sum(1 for count in freq if count % 2 == 1) <= 1


def wonderful_substrings_basic(word):
    n = len(word)
    count = 0
    for i in range(n):
        for j in range(i+1, n+1):
            if is_wonderful(word[i:j]):
                count += 1
    return count

print(wonderful_substrings_basic("aba"))

This solution in Python uses a nested loop to generate all possible substrings of the given word. The auxiliary function `is_wonderful` checks each substring to see if at most one character has an odd frequency, defining it as wonderful.

Complexity

Time Complexity: O(n^3),
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

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;
}
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
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Bitmask and Prefix Sum

Time Complexity: O(n * k),
Space Complexity: O(2^k).

Approach 2: Sliding Window (Basic)

Time Complexity: O(n^3),
Space Complexity: O(1).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Bitmask and Prefix SumO(n * 10) ≈ O(n)O(2^10)Best general solution. Efficient for large strings and expected in interviews.
Sliding Window (Basic)O(n^2)O(1)Useful for understanding the condition and brute-force reasoning before optimization.

Frequently asked questions

Is Number of Wonderful Substrings easy or hard?

The problem is rated Medium on LeetCode. The challenge comes from recognizing that substring validity depends only on odd/even parity and encoding that state using a bitmask. Once the parity insight is clear, the prefix counting solution becomes straightforward.

Number of Wonderful Substrings Python/Java solution

Most implementations maintain an integer mask and an array of size 1024 storing prefix counts. For every character, toggle its bit, add matches for the same mask, then check the 10 masks with one bit flipped. The same logic works across Python, Java, C++, C#, and JavaScript.

How to solve Number of Wonderful Substrings in O(n)?

Maintain a 10-bit mask representing odd/even counts of characters 'a' through 'j'. As you scan the string, update the mask using XOR. Count how many previous prefixes have the same mask (all characters even) and masks differing by exactly one bit (one odd character). Store prefix frequencies in an array of size 1024.

What is the best approach for Number of Wonderful Substrings?

The optimal approach uses a bitmask with prefix frequency counting. Each character toggles one of 10 bits representing odd/even frequency. A hash table or array tracks how many times each mask appeared, allowing you to count substrings where the parity mask differs by zero or one bit. This runs in O(n) time.

Is Number of Wonderful Substrings asked at Google/Amazon/Meta?

Parity-mask string problems similar to this appear in interviews at companies like Google and Amazon. The technique of encoding character parity with bitmasks and combining it with prefix frequency counting is a common interview pattern.

What data structure is used in Number of Wonderful Substrings?

The core data structure is a frequency map (often an array of size 1024) that stores how many times each bitmask has appeared. The algorithm also uses bit manipulation to represent character parity and a prefix-sum style traversal of the string.

What is the time complexity of Number of Wonderful Substrings?

The optimal solution runs in O(n * 10) time, which simplifies to O(n). For each character you check the current mask and the 10 masks formed by flipping one bit. Space complexity is O(2^10) because there are only 1024 possible parity states.

Comments

Now write it yourselfClose this page and solve Number of Wonderful Substrings in the editor, without looking.
Practise Number of Wonderful Substrings