1915. Number of Wonderful Substrings LeetCode Solution

In this guide, you will get 1915. Number of Wonderful Substrings LeetCode Solution with the best time and space complexity. The solution to Number of Wonderful Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Wonderful Substrings solution in C++
Number of Wonderful Substrings solution in Java
Number of Wonderful Substrings solution in Python
Additional Resources

1915. Number of Wonderful Substrings LeetCode Solution image

Problem Statement of Number of Wonderful Substrings

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

Complexity Analysis

Time Complexity: O(10n) = O(n)
Space Complexity: O(1024) = O(1)

1915. Number of Wonderful Substrings LeetCode Solution in C++

class Solution {
 public:
  long long wonderfulSubstrings(string word) {
    long ans = 0;
    int prefix = 0;           // the binary prefix
    vector<int> count(1024);  // the binary prefix count
    count[0] = 1;             // the empty string ""

    for (const char c : word) {
      prefix ^= 1 << c - 'a';
      // All the letters occur even number of times.
      ans += count[prefix];
      // ('a' + i) occurs odd number of times.
      for (int i = 0; i < 10; ++i)
        ans += count[prefix ^ 1 << i];
      ++count[prefix];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1915. Number of Wonderful Substrings LeetCode Solution in Java

class Solution {
  public long wonderfulSubstrings(String word) {
    long ans = 0;
    int prefix = 0;              // the binary prefix
    int[] count = new int[1024]; // the binary prefix count
    count[0] = 1;                // the empty string ""

    for (final char c : word.toCharArray()) {
      prefix ^= 1 << c - 'a';
      // All the letters occur even number of times.
      ans += count[prefix];
      // ('a' + i) occurs odd number of times.
      for (int i = 0; i < 10; ++i)
        ans += count[prefix ^ 1 << i];
      ++count[prefix];
    }

    return ans;
  }
}
// code provided by PROGIEZ

1915. Number of Wonderful Substrings LeetCode Solution in Python

class Solution:
  def wonderfulSubstrings(self, word: str) -> int:
    ans = 0
    prefix = 0  # the binary prefix
    count = [0] * 1024  # the binary prefix count
    count[0] = 1  # the empty string ""

    for c in word:
      prefix ^= 1 << ord(c) - ord('a')
      # All the letters occur even number of times.
      ans += count[prefix]
      # `c` occurs odd number of times.
      ans += sum(count[prefix ^ 1 << i] for i in range(10))
      count[prefix] += 1

    return ans
 # code by PROGIEZ