Minimize the count of characters to be added or removed to make String repetition of same substring | Function to find the minimum of the three numbers ; Function to find the minimum number operations required to convert string str1 to str2 using the operations ; Stores the results of subproblems ; Fill dp [ ] [ ] in bottom up manner ; If str1 is empty , then insert all characters of string str2 ; Minimum operations is j ; If str2 is empty , then remove all characters of string str2 ; Minimum operations is i ; If the last characters are same , then ignore last character ; If the last character is different , then find the minimum ; Perform one of the insert , remove and the replace ; Return the minimum number of steps required ; Function to find the minimum number of steps to modify the string such that first half and second half becomes the same ; Stores the minimum number of operations required ; Traverse the given string S ; Find the minimum operations ; Update the ans ; Print the result ; Driver Code
def getMin ( x , y , z ) : NEW_LINE INDENT return min ( min ( x , y ) , z ) NEW_LINE DEDENT def editDistance ( str1 , str2 , m , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( m + 1 ) ] NEW_LINE for i in range ( 0 , m + 1 ) : NEW_LINE INDENT for j in range ( 0 , n + 1 ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = j NEW_LINE DEDENT elif ( j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = i NEW_LINE DEDENT elif ( str1 [ i - 1 ] == str2 [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 + getMin ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ m ] [ n ] NEW_LINE DEDENT def minimumSteps ( S , N ) : NEW_LINE INDENT ans = 10 ** 10 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT S1 = S [ : i ] NEW_LINE S2 = S [ i : ] NEW_LINE count = editDistance ( S1 , S2 , len ( S1 ) , len ( S2 ) ) NEW_LINE ans = min ( ans , count ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT S = " aabb " NEW_LINE N = len ( S ) NEW_LINE minimumSteps ( S , N ) NEW_LINE