Number of Wonderful Substrings Solution

Number of wonderful substrings program is a recent addition, so let's explore a solution for the number of wonderful substrings program together.

Welcome back, visitor. In this post, I will be solving the 'number of wonderful substrings' problem, which is found on platforms like LeetCode, HackerEarth, and others. if you are looking for Beginner and Intermediate Level Interview Programs then do check those tags.

Reverse a linked list recursively in python

Understand : How to count the number of substrings?

What is Wonderful String:

A wonderful string is a string where only one letter occurs an odd number of times, and all other letters appear an even number of times. For instance, consider the string "ccjjc". Here, 'c' appears three times (odd), while 'j' appears twice (even). Thus, "ccjjc" is a wonderful string. However, in the string "ab", both 'a' and 'b' appear once each, violating the condition of a wonderful string.

Counting Wonderful Substrings:

To count the number of wonderful substrings in a given string, we must identify all substrings that satisfy the criteria of a wonderful string. For example, in the string "abab", there are several wonderful substrings: "aba", "bab", "abab" and more. Each of these substrings has only one letter occurring an odd number of times, making them wonderful. Therefore, the count of wonderful substrings in "abab" would be 7.

Check image illustration of wonderful strings and the process of identifying and counting wonderful substrings within a given string, as per the number of wonderful substrings problem.

Program : Number of Wonderful Substrings

Before delving into the programming aspect, it's essential to ensure clarity regarding the problem statement. If you have any doubts or require further clarification about the question or what needs to be found, please feel free to leave a comment to reach out to us. We're here to assist you and ensure your understanding before proceeding.

Please follow website page for understand step by step logic. there are six steps.

// program by interviewspreparation.com

private static long WonderfulSubstrings(string word)
{
    long ans = 0;
    int prefix = 0;           
    int[] count = new int[1024];  
    count[0] = 1;            

    foreach (char c in word)
    {
        int index = c - 'a';

        prefix ^= 1 << index;

        ans += count[prefix];

        for (int i = 0; i < 10; ++i)
        {
            ans += count[prefix ^ (1 << i)];
        }

        ++count[prefix];
    }

    return ans;
}