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, 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

    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