What is the time complexity of Number of Wonderful Substrings?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Number of Wonderful Substrings?

This problem uses Hash Table, String, Bit Manipulation, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Number of Wonderful Substrings?

Insight 1: Use bit manipulation to efficiently track the parity (even or odd count) of each character ('a' to 'j'). A mask can represent the parity of all characters, where the i-th bit represents the parity of the i-th character. Insight 2: The prefix sum concept can be adapted to this problem. Instead of storing the sum, we store the parity mask. The number of substrings ending at a given index with a specific parity mask is equal to the number of prefixes ending at a previous index with that parity mask.

Which companies ask LeetCode 1915. Number of Wonderful Substrings in interviews?

This problem is frequently asked at DE Shaw.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number of Wonderful Substrings - LeetCode 1915 Solution

Number of Wonderful Substrings - Complete Solution Guide

Number of Wonderful Substrings is LeetCode problem 1915, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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"

Detailed Explanation

The problem asks us to find the number of 'wonderful' substrings within a given string `word`. A 'wonderful' string is defined as a string where at most one character appears an odd number of times. The input string `word` consists only of lowercase English letters from 'a' to 'j'. We need to count all non-empty substrings of `word` and determine how many of them are 'wonderful'. Each occurrence of the same substring should be counted separately.

Solution Approach

The solution utilizes bit manipulation and a frequency count to efficiently determine the number of wonderful substrings. It iterates through the string, maintaining a bitmask representing the parity of each character encountered so far. The bitmask is updated using XOR (^) operations. For each character, the solution checks how many previous substrings have the same bitmask (meaning the substring between those indices has all characters appearing an even number of times) and how many substrings have a bitmask that differs by only one bit (meaning exactly one character appears an odd number of times). A `counts` array stores the number of times each bitmask has been seen so far.

Step-by-Step Algorithm

Step 1: Initialize a `counts` array of size 1024 (2^10) to store the frequency of each bitmask. Initialize `counts[0]` to 1 because an empty substring has a mask of 0 (all characters have even counts).
Step 2: Initialize a `result` variable to 0. This variable will store the total number of wonderful substrings.
Step 3: Initialize a `mask` variable to 0. This variable will store the bitmask representing the parity of characters encountered so far.
Step 4: Iterate through the input string `word` character by character.
Step 5: For each character, calculate its index by subtracting the ASCII value of 'a' from its ASCII value (e.g., 'b' - 'a' = 1).
Step 6: Update the `mask` by XORing it with `(1 << char_index)`. This toggles the bit corresponding to the character's index, effectively tracking the parity of the character.
Step 7: Increment the `result` by `counts[mask]`. This adds the number of substrings ending at the current index with all even character counts to the total.
Step 8: Iterate through the possible single-character odd counts (from 0 to 9). For each character index `i`, increment the `result` by `counts[mask ^ (1 << i)]`. This adds the number of substrings ending at the current index with only one odd character count to the total.
Step 9: Increment `counts[mask]` by 1 to update the frequency count of the current bitmask.
Step 10: After iterating through all characters, return the `result`.

Key Insights

Insight 1: Use bit manipulation to efficiently track the parity (even or odd count) of each character ('a' to 'j'). A mask can represent the parity of all characters, where the i-th bit represents the parity of the i-th character.
Insight 2: The prefix sum concept can be adapted to this problem. Instead of storing the sum, we store the parity mask. The number of substrings ending at a given index with a specific parity mask is equal to the number of prefixes ending at a previous index with that parity mask.
Insight 3: To check if a substring is wonderful, we need to determine if at most one character has an odd count. This can be achieved by either having all characters with even counts (mask = 0) or by having only one character with an odd count (only one bit set in the mask).

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Bit Manipulation, Prefix Sum.

Companies

Asked at: DE Shaw.

Number of Wonderful Substrings | LeetCode 1915

Medium

Hash Table String Bit Manipulation Prefix Sum

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public long wonderfulSubstrings(String word) {
        int[] counts = new int[1024];
        counts[0] = 1;
        long result = 0;
        int mask = 0;
        
        for (char charr : word.toCharArray()) {
            int char_index = charr - 'a';
            mask ^= (1 << char_index);
            
            result += counts[mask];
            
            for (int i = 0; i < 10; i++) {
                result += counts[mask ^ (1 << i)];
            }
            
            counts[mask] += 1;
        }
        
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1915: Number of Wonderful Substrings - Detailed explanation and solution approaches.

Topics

Hash Table String Bit Manipulation Prefix Sum

Companies

DE Shaw

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1915

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize a `counts` array of size 1024 (2^10) to store the frequency of each bitmask. Initialize `counts[0]` to 1 because an empty substring has a mask of 0 (all characters have even counts).
2
Step 2: Initialize a `result` variable to 0. This variable will store the total number of wonderful substrings.
3
Step 3: Initialize a `mask` variable to 0. This variable will store the bitmask representing the parity of characters encountered so far.
4
Step 4: Iterate through the input string `word` character by character.
5
Step 5: For each character, calculate its index by subtracting the ASCII value of 'a' from its ASCII value (e.g., 'b' - 'a' = 1).
6
Step 6: Update the `mask` by XORing it with `(1 << char_index)`. This toggles the bit corresponding to the character's index, effectively tracking the parity of the character.
7
Step 7: Increment the `result` by `counts[mask]`. This adds the number of substrings ending at the current index with all even character counts to the total.
8
Step 8: Iterate through the possible single-character odd counts (from 0 to 9). For each character index `i`, increment the `result` by `counts[mask ^ (1 << i)]`. This adds the number of substrings ending at the current index with only one odd character count to the total.
9
Step 9: Increment `counts[mask]` by 1 to update the frequency count of the current bitmask.
10
Step 10: After iterating through all characters, return the `result`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is determined by the linear iteration through the string. The inner loop iterating 10 times is a constant factor and does not affect the overall linear time complexity. The space complexity is constant because the size of the `counts` array is fixed and does not depend on the input string's length.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible substrings and then, for each substring, count the frequency of each character and check if it is a 'wonderful' string. The time complexity makes this not practical.

Time: O(n^2 * m) where n is the length of the string and m is the number of possible characters (10 in this case). The n^2 comes from generating all substrings and the m comes from counting characters in each substringSpace: O(m) to store the counts of each character for each substring analyzed

Trade-offs: Extremely inefficient compared to the bit manipulation approach, suitable only for very small input sizes.

✨

Key Insights

1Insight 1: Use bit manipulation to efficiently track the parity (even or odd count) of each character ('a' to 'j'). A mask can represent the parity of all characters, where the i-th bit represents the parity of the i-th character.
2Insight 2: The prefix sum concept can be adapted to this problem. Instead of storing the sum, we store the parity mask. The number of substrings ending at a given index with a specific parity mask is equal to the number of prefixes ending at a previous index with that parity mask.
3Insight 3: To check if a substring is wonderful, we need to determine if at most one character has an odd count. This can be achieved by either having all characters with even counts (mask = 0) or by having only one character with an odd count (only one bit set in the mask).

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string (not applicable as constraint specifies length >= 1)
Edge case 2: String with all the same characters: This case is handled correctly by the XOR operation and count updates. The bitmask will toggle as the same characters are processed and the substrings will be counted.
Edge case 3: String with all different characters: The algorithm correctly tracks each character's parity through XOR operations and increments the count based on at most one odd character.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not understanding the bit manipulation trick: Failing to see how XOR can be used to efficiently track the parity of each character is a common stumbling block. XOR is used because xoring a bit with 1 toggles that bit, thus we can track whether a letter occurs an even or odd amount of times.

✗Common mistake 2: Incorrectly calculating the number of substrings with at most one odd character: The inner loop must consider all possible single-character odd counts by XORing the current `mask` with each bit from 0 to 9 and then querying the `counts` array. Forgetting to consider that one odd value may occur is an error.

✗Common mistake 3: Integer overflow. In the C and Java solutions, the result needs to be a `long long` or `long` to avoid integer overflow when the number of wonderful substrings becomes large.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression: The principle of identifying patterns (like characters appearing even/odd times) can be extended to identifying redundant data in compression algorithms.

🏦Real-world scenario 2: Bioinformatics: Similar bit manipulation techniques are used in DNA sequence analysis to track specific gene expressions or mutations based on sequence patterns.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 24, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Number of Wonderful Substrings"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?