## PROBLEM LINK :

**Author : **Asim Krishna Prasad

**Tester : **Sarvesh Mahajan

## DIFFICULTY :

CAKEWALK

## PREREQUISITES :

Bitwise operations

## PROBLEM :

Given two sets of strings A and B, you have to find how many such pairs (A_{i}, B_{j}) exist such that concatenation of the two strings contains all the letters of English alphabet.

## EXPLANATION :

First there are a few observations :

- We don't need the whole string for computation. We just need to know if a particular alphabet is present in a particular string or not.
- Since we can loop over A x B, we only need a fast method to represent and concatenate two representations of strings

To solve this problem we can use bits to map if a particular alphabet is present in a string or not. So,

- A string will be represented as an integer value which has bits set corresponding to each distinct alphabet present in the string. Example : for string A : 1, for string AC : 5 = (101)
_{2}. - Now concatenation of two strings would be equivalent to taking bitwise-or of the corresponding integers. That is, if either one of the strings has a bit set, it would be set in the concatenated string.

To make the integer corresponding to a string :

```
int inLimit = strlen(str1);
int num = 0;
fl(j,0,inLimit)
{
int ele = int(str1[j]-'A');
num |= (1 << ele);
}
```

Now the answer is the number of pairs (A_{i} B_{j}) such that bitwise-or of them has 26 set bits from beginning or bitwise-or has value equal to ( (1 << 26) - 1).