Lexicographically smallest string which differs from given strings at exactly K indices | Python3 program for the above approach ; Function to find the string which differ at exactly K positions ; Initialise s3 as s2 ; Number of places at which s3 differ from s2 ; Minimum possible value is ceil ( d / 2 ) if it is not possible then - 1 ; Case 2 when K is less equal d ; X show the modification such that this position only differ from only one string ; Modify the position such that this differ from both S1 & S2 & decrease the T at each step ; Finding the character which is different from both S1 and S2 ; After we done T start modification to meet our requirement for X type ; Resultant string ; Case 1 when K > d In first step , modify all the character which are not same in S1 and S3 ; Finding character which is different from both S1 and S2 ; Our requirement not satisfied by performing step 1. We need to modify the position which matches in both string ; Finding the character which is different from both S1 and S2 ; Resultant string ; Driver Code ; Given two strings ; Function call
arr = [ ' a ' , ' b ' , ' c ' ] NEW_LINE def findString ( n , k , s1 , s2 ) : NEW_LINE INDENT s3 = s2 NEW_LINE s3 = list ( s3 ) NEW_LINE d = 0 NEW_LINE for i in range ( len ( s1 ) ) : NEW_LINE INDENT if ( s1 [ i ] != s2 [ i ] ) : NEW_LINE INDENT d += 1 NEW_LINE DEDENT DEDENT if ( ( d + 1 ) // 2 > k ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT if ( k <= d ) : NEW_LINE INDENT X = d - k NEW_LINE T = 2 * k - d NEW_LINE for i in range ( len ( s3 ) ) : NEW_LINE INDENT if ( s1 [ i ] != s2 [ i ] ) : NEW_LINE INDENT if ( T > 0 ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE INDENT if ( arr [ j ] != s1 [ i ] and arr [ j ] != s2 [ i ] ) : NEW_LINE INDENT s3 [ i ] = arr [ j ] NEW_LINE T -= 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT elif ( X > 0 ) : NEW_LINE INDENT s3 [ i ] = s1 [ i ] NEW_LINE X -= 1 NEW_LINE DEDENT DEDENT DEDENT print ( " " . join ( s3 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( len ( s1 ) ) : NEW_LINE INDENT if ( s1 [ i ] != s3 [ i ] ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE INDENT if ( arr [ j ] != s1 [ i ] and arr [ j ] != s3 [ i ] ) : NEW_LINE INDENT s3 [ i ] = arr [ j ] NEW_LINE k -= 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( len ( s1 ) ) : NEW_LINE INDENT if ( s1 [ i ] == s3 [ i ] and k ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE INDENT if ( arr [ j ] != s1 [ i ] and arr [ j ] != s3 [ i ] ) : NEW_LINE INDENT s3 [ i ] = arr [ j ] NEW_LINE k -= 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT print ( " " . join ( s3 ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 NEW_LINE k = 2 NEW_LINE S1 = " zzyy " NEW_LINE S2 = " zxxy " NEW_LINE findString ( N , k , S1 , S2 ) NEW_LINE DEDENT