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 ba=a xor b // a xor b xor a=b ….value of b stored in a

What are the bitwise operators?

There are six types of bitwise operators. These areAND(&), OR(|), NOT(~), XOR(^), Left Shift( >)

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 andThe value of INT_MIN is -2147483648.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Brute Force Approach

2.1.

Pseudo Code

2.2.

Implementation in C++

2.2.1.

Complexity Analysis

Efficient Approach

3.1.

Implementation in C++

3.1.1.

Complexity Analysis

FAQs

Key takeaways

Last Updated: Mar 27, 2024

Number of wonderful substrings

Author Ayush Tiwari

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

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 mask = 0;
    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
        ans += seen[mask];
        for (int j = 0; j < 26; ++j)
        {
          // will count the substrings that have exactly 1 letter that is used 
            ans += seen[mask ^ (1 << j)];
        }
        seen[mask]++;
    }
    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 complexity - O(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

Read about Bitwise Operators in C here.

FAQs

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