Count the nodes of a tree whose weighted string does not contain any duplicate characters | Python3 implementation of the approach ; Function that returns true if the string contains unique characters ; Function to perform dfs ; If weight of the current node node contains unique characters ; Driver code ; Weights of the node ; Edges of the tree
cnt = 0 NEW_LINE graph = [ [ ] for i in range ( 100 ) ] NEW_LINE weight = [ 0 ] * 100 NEW_LINE def uniqueChars ( x ) : NEW_LINE INDENT mp = { } NEW_LINE n = len ( x ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if x [ i ] not in mp : NEW_LINE INDENT mp [ x [ i ] ] = 0 NEW_LINE DEDENT mp [ x [ i ] ] += 1 NEW_LINE DEDENT if ( len ( mp ) == len ( x ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def dfs ( node , parent ) : NEW_LINE INDENT global cnt , x NEW_LINE if ( uniqueChars ( weight [ node ] ) ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT for to in graph [ node ] : NEW_LINE INDENT if ( to == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( to , node ) NEW_LINE DEDENT DEDENT x = 5 NEW_LINE weight [ 1 ] = " abc " NEW_LINE weight [ 2 ] = " aba " NEW_LINE weight [ 3 ] = " bcb " NEW_LINE weight [ 4 ] = " moh " NEW_LINE weight [ 5 ] = " aa " NEW_LINE graph [ 1 ] . append ( 2 ) NEW_LINE graph [ 2 ] . append ( 3 ) NEW_LINE graph [ 2 ] . append ( 4 ) NEW_LINE graph [ 1 ] . append ( 5 ) NEW_LINE dfs ( 1 , 1 ) NEW_LINE print ( cnt ) NEW_LINE