Minimum number of pairs required to make two strings same | Python3 implementation of the approach ; Function which will check if there is a path between a and b by using BFS ; Function to return the minimum number of pairs ; To store the count of pairs ; Iterating through the strings ; Check if we can add an edge in the graph ; Return the count of pairs ; Driver code
from collections import defaultdict , deque NEW_LINE def Check_Path ( a , b , G ) : NEW_LINE INDENT visited = defaultdict ( bool ) NEW_LINE queue = deque ( ) NEW_LINE queue . append ( a ) NEW_LINE visited [ a ] = True NEW_LINE while queue : NEW_LINE INDENT n = queue . popleft ( ) NEW_LINE if n == b : NEW_LINE INDENT return True NEW_LINE DEDENT for i in list ( G [ n ] ) : NEW_LINE INDENT if visited [ i ] == False : NEW_LINE INDENT queue . append ( i ) NEW_LINE visited [ i ] = True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def countPairs ( s1 , s2 , G ) : NEW_LINE INDENT name = defaultdict ( bool ) NEW_LINE count = 0 NEW_LINE for i in range ( x ) : NEW_LINE INDENT a = s1 [ i ] NEW_LINE b = s2 [ i ] NEW_LINE if a in G and b not in G and a != b : NEW_LINE INDENT G [ a ] . append ( b ) NEW_LINE G [ b ] . append ( a ) NEW_LINE count += 1 NEW_LINE DEDENT elif b in G and a not in G and a != b : NEW_LINE INDENT G [ b ] . append ( a ) NEW_LINE G [ a ] . append ( b ) NEW_LINE count += 1 NEW_LINE DEDENT elif a not in G and b not in G and a != b : NEW_LINE INDENT G [ a ] . append ( b ) NEW_LINE G [ b ] . append ( a ) NEW_LINE count += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if not Check_Path ( a , b , G ) and a != b : NEW_LINE INDENT G [ a ] . append ( b ) NEW_LINE G [ b ] . append ( a ) NEW_LINE count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s1 = " abb " NEW_LINE s2 = " dad " NEW_LINE x = len ( s1 ) NEW_LINE G = defaultdict ( list ) NEW_LINE print ( countPairs ( s1 , s2 , G ) ) NEW_LINE DEDENT