Pairs of strings which on concatenating contains each character of " string " | PHP 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
< ? php $ MAX = 64 ; function getBitmask ( $ s ) { $ temp = 0 ; for ( $ j = 0 ; $ j < strlen ( $ s ) ; $ 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 ; } function countPairs ( $ arr , $ n ) { $ bitMask = array_fill ( 0 , $ GLOBALS [ ' MAX ' ] , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ bitMask [ getBitmask ( $ arr [ $ i ] ) ] ++ ; $ cnt = 0 ; for ( $ i = 0 ; $ i < $ GLOBALS [ ' MAX ' ] ; $ i ++ ) { for ( $ j = $ i ; $ j < $ GLOBALS [ ' MAX ' ] ; $ j ++ ) { if ( ( $ i $ j ) == ( $ GLOBALS [ ' MAX ' ] - 1 ) ) { if ( $ i == $ j ) $ cnt += floor ( ( $ bitMask [ $ i ] * $ bitMask [ $ i ] - 1 ) / 2 ) ; else $ cnt += ( $ bitMask [ $ i ] * $ bitMask [ $ j ] ) ; } } } return $ cnt ; } $ arr = array ( " strrr " , " string " , " gstrin " ) ; $ n = count ( $ arr ) ; echo countPairs ( $ arr , $ n ) ; ? >