# Solving Leetcode Interviews in Seconds with AI: Number of Wonderful Substrings


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1915" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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

	# Explanation
	Here's the solution to the problem, along with a breakdown of the approach:

*   **Prefix XOR:** We'll maintain a prefix XOR sum where each bit in the XOR sum represents whether a character ('a' to 'j') has appeared an odd number of times so far. The `i`-th bit is 1 if the `i`-th character has appeared an odd number of times and 0 if it has appeared an even number of times.

*   **Counting Wonderful Substrings:** A substring from index `i` to `j` is wonderful if the XOR sum from `i` to `j` has at most one bit set.  We can calculate the XOR sum of a substring using `prefix_xor[j] ^ prefix_xor[i-1]` (or just `prefix_xor[j]` if i is 0). We use a hash map to store the number of times each prefix XOR sum has appeared so far.

*   **Checking for "One Bit Set":**  We iterate through each possible prefix XOR sum and check if flipping a single bit in it results in another prefix XOR sum we've already seen.  This efficiently checks if a substring is wonderful.

*   **Runtime Complexity:** O(N), where N is the length of the input string, due to the single pass through the string.
*   **Storage Complexity:** O(1), because the prefix XOR can only have 2^10 different values.

	
	# Code
	```python
	def wonderful_substrings(word: str) -> int:
    """
    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.
    """
    counts = {0: 1}  # Initialize count for empty prefix (XOR 0)
    prefix_xor = 0
    ans = 0

    for char in word:
        # Update prefix XOR sum
        prefix_xor ^= (1 << (ord(char) - ord('a')))

        # Add count of current prefix XOR (substring with even counts of all chars)
        ans += counts.get(prefix_xor, 0)

        # Check for substrings with one odd count
        for i in range(10):
            mask = 1 << i
            flipped_xor = prefix_xor ^ mask
            ans += counts.get(flipped_xor, 0)

        # Update prefix XOR count
        counts[prefix_xor] = counts.get(prefix_xor, 0) + 1

    return ans
	```