Count of distinct groups of strings formed after performing equivalent operation | Function to perform the find operation to find the parent of a disjoint set ; Function to perform union operation of disjoint set union ; Find the parent of node a and b ; Update the rank ; Function to find the number of distinct strings after performing the given operations ; Stores the parent elements of the sets ; Stores the rank of the sets ; Update parent [ i ] to i ; Stores the total characters traversed through the strings ; Stores the current characters traversed through a string ; Update current [ i ] to false ; Update current [ ch - ' a ' ] to true ; Check if current [ j ] is true ; Update total [ j ] to true ; Add arr [ i ] [ 0 ] - ' a ' and j elements to same set ; Stores the count of distinct strings ; Check total [ i ] is true and parent of i is i only ; Increment the value of distCount by 1 ; Print the value of distCount ; Driver Code
def Find ( parent , a ) : NEW_LINE INDENT if parent [ a ] == a : NEW_LINE INDENT parent [ a ] = a NEW_LINE return parent [ a ] NEW_LINE DEDENT else : NEW_LINE INDENT parent [ a ] = Find ( parent , parent [ a ] ) NEW_LINE return parent [ a ] NEW_LINE DEDENT DEDENT def Union ( parent , rank , a , b ) : NEW_LINE INDENT a = Find ( parent , a ) NEW_LINE b = Find ( parent , b ) NEW_LINE if ( rank [ a ] == rank [ b ] ) : NEW_LINE INDENT rank [ a ] += 1 NEW_LINE DEDENT if ( rank [ a ] > rank [ b ] ) : NEW_LINE INDENT parent [ b ] = a NEW_LINE DEDENT else : NEW_LINE INDENT parent [ a ] = b NEW_LINE DEDENT DEDENT def numOfDistinctStrings ( arr , N ) : NEW_LINE INDENT parent = [ 0 for _ in range ( 27 ) ] NEW_LINE rank = [ 0 for _ in range ( 27 ) ] NEW_LINE for j in range ( 0 , 27 ) : NEW_LINE INDENT parent [ j ] = j NEW_LINE DEDENT total = [ False for _ in range ( 26 ) ] NEW_LINE current = [ False for _ in range ( 26 ) ] NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , 26 ) : NEW_LINE INDENT current [ j ] = False NEW_LINE DEDENT for ch in arr [ i ] : NEW_LINE INDENT current [ ord ( ch ) - ord ( ' a ' ) ] = True NEW_LINE DEDENT for j in range ( 0 , 26 ) : NEW_LINE INDENT if ( current [ j ] ) : NEW_LINE INDENT total [ j ] = True NEW_LINE Union ( parent , rank , ord ( arr [ i ] [ 0 ] ) - ord ( ' a ' ) , j ) NEW_LINE DEDENT DEDENT DEDENT distCount = 0 NEW_LINE for i in range ( 0 , 26 ) : NEW_LINE INDENT if ( total [ i ] and Find ( parent , i ) == i ) : NEW_LINE INDENT distCount += 1 NEW_LINE DEDENT DEDENT print ( distCount ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ " a " , " ab " , " b " , " d " ] NEW_LINE N = len ( arr ) NEW_LINE numOfDistinctStrings ( arr , N ) NEW_LINE DEDENT