Number of wonderful substrings program is a recent addition, so let’s explore a solution for the number of beautiful 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.
FREE : If you’re a new visitor preparing for an interview and need help or want to request a new question, you can use the form on the right side to ask your question. It’s free and doesn’t require signing in. Alternatively, you can ask in our Quora space, which is also free, and you’ll receive a response within 24 hours. Go ahead and check it out!
Table of Contents
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 beautiful 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.
Step 1
As usual, in the initial step, I’ll create variables to be used in the program. I’ve initialized a long variable named ‘ans’, an integer variable named ‘prefix’, an integer array of size 1024 named ‘count’, and by default, the program will return ‘ans’.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
long ans = 0;
int prefix = 0;
int[] count = new int[1024];
return ans;
}Step 2
In the second step, I’ll assign 0 to the first element of our integer array named ‘count’. Then, I’ll set up a foreach loop to iterate through all the characters in the given string.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
long ans = 0;
int prefix = 0;
int[] count = new int[1024];
count[0] = 1;
foreach (char c in word)
{
}
return ans;
}Step 3
In the third step, we’ll delve into the core logic of the program. Keep your focus here, as this is where our algorithm begins.
In this step, I’ll create a local integer variable named ‘index’. As the name suggests, we’ll use it to store the index of characters as we iterate through the string.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
long ans = 0;
int prefix = 0;
int[] count = new int[1024];
count[0] = 1;
foreach (char c in word)
{
int index = c - 'a';
}
return ans;
}Now, I know you’re wondering why I’ve written ‘int index = c – ‘a’. Am I correct? The answer is quite straightforward. We use ASCII to find the index of a character between ‘a’ to ‘j’. If you’re not familiar with ASCII, here’s a quick explanation: computers understand only 0s and 1s, and to store character values, they use numeric formats. For example, the ASCII value of “A” is 65. Therefore, if I subtract the ASCII values of two characters, I get the distance/index between them. check below example
static void Main(string[] args)
{
//program by interviewspreparation.com
char one = 'b';
Console.WriteLine(one-'a');
//output is 1, if you change 'b' to 'c' then your answer will 2. Understood?
}Step 4
In this step, I’ll employ bit manipulation to update ‘prefix’ using the XOR operator and the left shift operator.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
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;
}
return ans;
}The expression prefix ^= 1 << index; is a combination of the bitwise XOR operator (^) and the left shift operator (<<). Let’s break it down: 1 << index This part shifts the binary digit 1 to the left by index positions. For example, if index is 3, 1 << 3 would result in binary 1000 (which is 8 in decimal). So, 1 << index creates a value where the only bit set to 1 is at the index position from the right. prefix ^= 1 << index: This line performs a bitwise XOR operation between prefix and the value obtained from 1 << index. If the index-th bit of prefix is currently 0, it will be set to 1. If the index-th bit of prefix is currently 1, it will be toggled to 0.
Step 5
In this step, we increment our answer by the value at the index of our integer array. In this case, the index is represented by our ‘prefix’ variable.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
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];
}
return ans;
}Step 6
Now, in the sixth step, I’ll create a for loop that starts with 0 and ends at 10. Here, 10 is not a magic number; it represents the length from ‘a’ to ‘j’, encompassing all possible characters. Within this loop, we’ll calculate a new value by flipping one bit in the prefix number. Then, we’ll check how many times we’ve encountered this new value before, and we’ll add that count to our answer. Finally, at the end of each iteration of the foreach loop, we’ll increase the corresponding element in the integer array named ‘count’.
private static long WonderfulSubstrings(string word)
{
//program by interviewspreparation.com
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;
}Summarizing Solution of number of wonderful substrings program
- Initialise variables: ‘ans’ as a long, ‘prefix’ as an int, and ‘count’ as an int array of size 1024, with ‘ans’ set to return by default.
- Assign 0 to the first element of the ‘count’ array and set up a foreach loop to iterate through all characters in the given string.
- Create a local int variable named ‘index’ to store the index of characters using ASCII values.
- Update ‘prefix’ using bit manipulation (XOR and left shift operators).
- Increment ‘ans’ by the value at the index of the ‘count’ array, using ‘prefix’ as the index.
- Create a for loop iterating from 0 to 10, representing the length from ‘a’ to ‘j’. Calculate a new value by flipping one bit in the ‘prefix’ number. Add the count of occurrences of this new value to ‘ans’. Increase the corresponding element in the ‘count’ array at the end of each foreach loop iteration.