Minimum Operations

Moderate

0/80

Average time to solve is 30m

0 upvote

Problem statement

You are given two strings, 'S' and 'T' of lengths 'N' and 'M' respectively. You have to find the minimum number of operations required to make both strings equal.

The operations you can perform on both strings are:

1- Insert a character.
2- Replace a character with any character.
3- Delete a character.

For Example :

Consider S = 'this' and T = 'the'. The minimum operations required to make strings equal are:
1- Delete ‘s’ from the string S. Hence the string S becomes ‘thi’.
2- Replace the character ‘i’ with ‘e’ in the string S. Hence the string S becomes ‘the’.

The minimum number of operations required is 2. Hence the answer is 2.

Note:

Strings don't contain spaces in between.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the string 'S' of length 'N'.

The second line of the input contains the String 'T' of length 'M'.

Output Format:

The only line of output prints the minimum number of operations required.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints:

0 <= N <= 10 ^ 3
0 <= M <= 10 ^ 3

Time Limit : 1 sec

Sample Input 1 :

raman
amit

Sample Output 1 :

Explanation For Sample Input 1 :

 In this input ,string S = ‘raman’ and string T = ‘amit’. The minimum operations required to make string S equal to string T are:
1- Delete ‘r’  from the string S. Hence the string S becomes ‘aman’
2- Replace the character ‘a’ with ‘i’ in the string S. Hence  the string ‘S’ becomes ‘amin’ 
3- Replace the character ‘n’ with ‘t’ in the string S. Hence  the string ‘S’ becomes ‘amit’

The minimum number of operations required is 3. Hence the answer is 3.

Sample Input 2 :

whgtdwhgtdg
aswcfg

Sample Output 2 :

Approaches (1)

Approach 1

Iterative DP

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Operations

Console