Number of Wonderful Substrings - Practice Coding Problems

Number of Wonderful Substrings - 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.

Input & Output

Example 1 — Basic Wonderful String

$ Input: word = "aba"

› Output: 4

💡 Note: Four wonderful substrings: "a" (index 0), "b" (index 1), "a" (index 2), and "aba" (indices 0-2). All single characters are wonderful, and "aba" has 'a' appearing 2 times (even) and 'b' appearing 1 time (odd) - at most one odd count.

Example 2 — All Single Characters

$ Input: word = "aabb"

› Output: 9

💡 Note: Single character substrings: "a", "a", "b", "b" (4 total). Two character substrings: "aa", "ab", "bb" (3 total). Three character: "aab", "abb" (2 total). Four character: "aabb" (1 total). Total: 4+3+2+0 = 9 wonderful substrings.

Example 3 — No Wonderful Multi-Character Substrings

$ Input: word = "he"

› Output: 2

💡 Note: Only the single character substrings "h" and "e" are wonderful. The substring "he" has both characters appearing once (2 odd counts > 1), so it's not wonderful.

Constraints

1 ≤ word.length ≤ 10⁵
word consists of lowercase English letters from 'a' to 'j'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "aba" with characters from a-j

Substring Generation

Find all contiguous substrings and check frequency patterns

Wonderful Check

Count substrings with ≤1 character having odd frequency

Key Takeaway

🎯 Key Insight: Use bitmasks to efficiently track character frequency parity and count wonderful substrings in O(n) time

Asked in

f Facebook 35 G Google 28 a Amazon 22

The key insight is to use bit manipulation to efficiently track character frequency parity. Each bit in a mask represents whether a character appears an odd number of times. Two substrings with the same mask or masks differing by exactly one bit form wonderful substrings. Best approach uses hash map with bitmasks: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Frequency Tracking	O(n²)	O(1)	Use running frequency counts to efficiently check substrings without recalculating
Brute Force - Check All Substrings	O(n³)	O(1)	Generate all substrings and count character frequencies to check if wonderful
Optimal Bit Manipulation with Hash Map	O(n)	O(n)	Use bitmask to represent character parity states and hash map to count prefix states

Prefix Sum with Frequency Tracking — Algorithm Steps

For each starting position i
Extend substring from i to j, updating frequencies incrementally
Check if current substring [i,j] is wonderful
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin from each starting index

Extend & Update

Add one character at a time, updating frequencies

Check Wonderful

Test if current substring is wonderful

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(char* word) {
    int n = strlen(word);
    long long count = 0;
    
    // For each starting position
    for (int i = 0; i < n; i++) {
        int freq[10] = {0};
        
        // Extend substring from position i
        for (int j = i; j < n; j++) {
            // Update frequency for current character
            freq[word[j] - 'a']++;
            
            // Check if current substring [i,j] is wonderful
            int oddCount = 0;
            for (int k = 0; k < 10; k++) {
                if (freq[k] % 2 == 1) {
                    oddCount++;
                }
            }
            
            if (oddCount <= 1) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char word[100001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;  // Remove newline
    
    long long result = solution(word);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops to generate all substrings, but frequency updates are O(1)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using fixed-size frequency array for 10 characters

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Frequency Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler