1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Pseudo Code
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Efficient Approach
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

# Number of wonderful substrings

Ayush Tiwari
0 upvote

## Introduction

### Problem Statement

Given a string 's' of length n, You have to find the number of non-empty wonderful substrings in 's'.

wonderful string is a string where at most, one letter appears an odd number of times, i.e., in whole, there is at most letter whose frequency is odd.
Example - "aabba", "zzz", "ccjjpp" is a wonderful string where "zzza", "ab" is not a wonderful string.

substring of s is a non-empty string x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|).

Let's take an example to understand this problem better.

### Sample Examples

Example 1:

``````Given String - 'bbcc'
Output - 9``````

Explanation:

Wonderful substrings of length one = “b”,”b”,”c”,”c”, count = 4
Wonderful substrings of length two = “bb”,”cc”, count = 2
Wonderful substrings of length three = “bbc”,”bcc”, count = 2
Wonderful substrings of length four = “bbcc”, count = 1

So, total wonderful substrings in given string = 9

Example 2:

``````Given String - 'pq'
Output - 2``````

Explanation:

Wonderful substrings of length one = “p”,”q”,, count = 2
Wonderful substrings of length two = 0

So, total wonderful substrings in given string = 2

Example 3:

``````Given String - 'z'
Output - 1``````

## Brute Force Approach

The brute force approach of this problem is finding all substrings, and for every substring, check substring is wonderful or not, i.e., where at most one letter appears an odd number of times.

### Pseudo Code

``````bool checkWonderful(string p)
n->size of string p
count[26]={0}
countOdd->0
loop(i=0 to n-1)
count[p[i]-’a’]++;
loop(i=0 to 25)
if(count[i] is odd)
countOdd++
if(countOdd<=1)
return true
else
return false

int countWonderfulString(string s)
n->size of string s
ans->0
loop(i=0 to n-1)
loop(j=i to n-1)
string p = s[i,j] // s[i,j]= sisi+1si+2…sj
if(checkWonderful(p))
ans++
return ans``````

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
// function check the string is wonderful or not
bool checkWonderful(string p)
{
int n = p.size();
int count[26] = {0};
int oddCount = 0;
for (int i = 0; i < n; i++)
count[p[i] - 'a']++;
for (int i = 0; i < 26; i++)
{
if (count[i] % 2 != 0)
oddCount++;
}
if (oddCount <= 1)
return true;
else
return false;
}
// function finds the number of wondeful sunstring
int countWonderfulString(string s)
{
int n = s.size();
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// substring from i to j
string p = s.substr(i, j - i + 1);
if (checkWonderful(p))
ans++;
}
}
return ans;
}
// driver code
int main()
{
string s;
cin >> s;
int ans = countWonderfulString(s);
cout << "Number of Wonderful substrings: " << ans;
}``````

Input and Output:

Input

``bbcc``

Output

``Number of Wonderful substrings: 9``

#### Complexity Analysis

Time complexityO(N^3). Finding all substring O(n^2) and for every substring, it takes O(n) to check substring is wonderful or not.

Space complexity - O(1).  No extra space required

Also check out - Substr C++ and Euclid GCD Algorithm

## Efficient Approach

This is a typical use of bitmasks. The idea is like this: we use a bitmask to indicate what characters are used the odd number of times, and we use a hashmap to keep track of previously seen bitmasks.

``````For example, let's consider the example "aba"
"" -> bitmask will be 0000…00000 ('a' - 'z' 26 characters as specified in the problem)
"a" -> bitmask will be 0000…000001, meaning a is used an odd number of times.
"ab" -> bitmask will now be 000000…0011, meaning both a and b are used an odd number of times.
"aba" -> bitmask will be 0000…000010.``````

In each iteration, we will increment the hashmap[bitmask] by one, meaning we have seen this bitmask before.

ans += seen[mask]; will count the substrings that have all letters used even number of times.
ans += seen[mask ^ (1<<j)]; will count the substrings that have exactly one letter that is used an odd number of times.

Time complexity will be O(26*N) = O(N).

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
// function finds the number of wondeful sunstring
int countWonderfulString(string s)
{
unordered_map<int, int> seen;
seen[0] = 1;
int ans = 0;
for (int i = 0; i < s.size(); ++i)
{
mask ^= (1 << (s[i] - 'a'));
// will count the substrings that have all letters used even number of times
for (int j = 0; j < 26; ++j)
{
// will count the substrings that have exactly 1 letter that is used
ans += seen[mask ^ (1 << j)];
}
}
return ans;
}
// driver code
int main()
{
string s;
cin >> s;
int ans = countWonderfulString(s);
cout << "Number of Wonderful substrings: " << ans;
}``````

Input and Output:

Input

``bbcc``

Output

``Number of Wonderful substrings: 9Time complexity - O(26*N). For each character in string s, we check for 26 characters.``

#### Complexity Analysis

Time complexityO(26*N). For each character in string s, we check for 26 characters.

Space complexity - O(26)=O(1).  Store the character in the map

## FAQs

1. How to swap two numbers using xor?
Let two numbers a and b.
a=a xor b
b=a xor b // a xor b xor b = a….value of a stored in b
a=a xor b // a xor b xor a=b ….value of b stored in a

2. What are the bitwise operators?
There are six types of bitwise operators. These are
AND(&), OR(|), NOT(~), XOR(^), Left Shift(<<), Right Shift(>>)

3. What is the largest and the smallest value of an integer in C++?
INT_MAX denotes the largest integer value in C++, and INT_MIN represents
the smallest integer value.
The value of INT_MAX is 2147483647 and
The value of INT_MIN is -2147483648.

## Key takeaways

In this article, we’ve discussed theNumber of wonderful substrings. Here an effective method has been used with the help of bitmasking. This is a crucial topic, and there are numerous exciting problems related to this topic.

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

Check out this problem - Multiply Strings

To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Coding and practicing in Code studio.
Happy Coding!

Live masterclass