Longest Common Subsequence ( LCS ) by repeatedly swapping characters of a string with characters of another string | Function to find the length of LCS possible by swapping any character of a with that of another string ; Store the size of the strings ; Stores frequency of characters ; Iterate over characters of the A ; Update frequency of character A [ i ] ; Iterate over characters of the B ; Update frequency of character B [ i ] ; Store the count of all pairs of similar characters ; Traverse the array freq [ ] ; Update cnt ; Print the minimum of cnt , N and M ; Driver Code ; Given strings
def lcsBySwapping ( A , B ) : NEW_LINE INDENT N = len ( A ) NEW_LINE M = len ( B ) NEW_LINE freq = [ 0 ] * 26 NEW_LINE for i in range ( len ( A ) ) : NEW_LINE INDENT freq [ ord ( A [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( len ( B ) ) : NEW_LINE INDENT freq [ ord ( B [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT cnt = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT cnt += freq [ i ] // 2 NEW_LINE DEDENT print ( min ( cnt , min ( N , M ) ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = " abdeff " NEW_LINE B = " abbet " NEW_LINE lcsBySwapping ( A , B ) NEW_LINE DEDENT