Maximize product of lengths of strings having no common characters | Function to count the number of set bits in the integer n ; Stores the count of set bits in n ; Return the count ; Function to find the maximum product of pair of strings having no common characters ; Stores the integer equivalent of the strings ; Traverse the array of strings ; Traverse the current string ; Store the current bit position in bits [ i ] ; Store the required result ; Traverse the array , bits [ ] to get all unique pairs ( i , j ) ; Check whether the strings have no common characters ; Update the overall maximum product ; Print the maximum product ; Driver Code
def countSetBits ( n ) : NEW_LINE INDENT count = 0 NEW_LINE while ( n > 0 ) : NEW_LINE INDENT count += n & 1 NEW_LINE n >>= 1 NEW_LINE DEDENT return count NEW_LINE DEDENT def maximumProduct ( words ) : NEW_LINE INDENT bits = [ 0 for i in range ( len ( words ) ) ] NEW_LINE for i in range ( len ( words ) ) : NEW_LINE INDENT for j in range ( len ( words [ i ] ) ) : NEW_LINE INDENT bits [ i ] = bits [ i ] | 1 << ( ord ( words [ i ] [ j ] ) - 97 ) NEW_LINE DEDENT DEDENT result = 0 NEW_LINE for i in range ( len ( bits ) ) : NEW_LINE INDENT for j in range ( i + 1 , len ( bits ) ) : NEW_LINE INDENT if ( ( bits [ i ] & bits [ j ] ) == 0 ) : NEW_LINE INDENT L = countSetBits ( bits [ i ] ) NEW_LINE R = countSetBits ( bits [ j ] ) NEW_LINE result = max ( L * R , result ) NEW_LINE DEDENT DEDENT DEDENT print ( result ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ " abcw " , " baz " , " foo " , " bar " , " xtfn " , " abcdef " ] NEW_LINE maximumProduct ( arr ) NEW_LINE DEDENT