Pairs of strings which on concatenating contains each character of " string " | C ++ implementation of the approach ; Function to return the bitmask for the string ; Function to return the count of pairs ; bitMask [ i ] will store the count of strings from the array whose bitmask is i ; To store the count of pairs ; MAX - 1 = 63 i . e . 111111 in binary ; arr [ i ] cannot make s pair with itself i . e . ( arr [ i ] , arr [ i ] ) ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  64 NEW_LINE int getBitmask ( string s ) { int temp = 0 ; for ( int j = 0 ; j < s . length ( ) ; j ++ ) { if ( s [ j ] == ' s ' ) { temp = temp | ( 1 ) ; } else if ( s [ j ] == ' t ' ) { temp = temp | ( 2 ) ; } else if ( s [ j ] == ' r ' ) { temp = temp | ( 4 ) ; } else if ( s [ j ] == ' i ' ) { temp = temp | ( 8 ) ; } else if ( s [ j ] == ' n ' ) { temp = temp | ( 16 ) ; } else if ( s [ j ] == ' g ' ) { temp = temp | ( 32 ) ; } } return temp ; } int countPairs ( string arr [ ] , int n ) { int bitMask [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) bitMask [ getBitmask ( arr [ i ] ) ] ++ ; int cnt = 0 ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = i ; j < MAX ; j ++ ) { if ( ( i j ) == ( MAX - 1 ) ) { if ( i == j ) cnt += ( ( bitMask [ i ] * bitMask [ i ] - 1 ) / 2 ) ; else cnt += ( bitMask [ i ] * bitMask [ j ] ) ; } } } return cnt ; } int main ( ) { string arr [ ] = { " strrr " , " string " , " gstrin " } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countPairs ( arr , n ) ; return 0 ; }