Minimum changes required to make first string substring of second string | Python3 program to find the minimum number of characters to be replaced in string S2 , such that S1 is a substring of S2 ; Function to find the minimum number of characters to be replaced in string S2 , such that S1 is a substring of S2 ; Get the sizes of both strings ; Traverse the string S2 ; From every index in S2 , check the number of mis - matching characters in substring of length of S1 ; Take minimum of prev and current mis - match ; return answer ; Driver Code
import sys NEW_LINE def minimumChar ( S1 , S2 ) : NEW_LINE INDENT n , m = len ( S1 ) , len ( S2 ) NEW_LINE ans = sys . maxsize NEW_LINE for i in range ( m - n + 1 ) : NEW_LINE INDENT minRemovedChar = 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( S1 [ j ] != S2 [ i + j ] ) : NEW_LINE INDENT minRemovedChar += 1 NEW_LINE DEDENT DEDENT ans = min ( minRemovedChar , ans ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 = " abc " NEW_LINE S2 = " paxzk " NEW_LINE print ( minimumChar ( S1 , S2 ) ) NEW_LINE DEDENT