## Introduction

### Problem Statement

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

A **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.

A **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 complexity** - **O(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__