Problem 1: Minimum Operations to Make Two Strings Equal

Given two strings s and t, determine the minimum number of operations required to make them identical by deleting characters from either string.

The approach involves identifying the longest common subsequence (LCS) between the two strings. Once the LCS length is known, the total deletions needed can be computed as:

(deletions from s) + (deletions from t)
= (length of s - LCS length) + (length of t - LCS length)

Implementation using dynamic programming:

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return (len1 - dp[len1][len2]) + (len2 - dp[len1][len2]);
    }
}

Problem 2: Edit Distance Between Two Strings

This problem calculates the minimum number of operations required to convert one string into another. Allowed operations are insert, delete, and replace.

We define dp[i][j] as the minimum edit distance between the first i characters of s and the first j characters of t.

Transitions depend on character comparison:

• If s[i-1] == t[j-1]: no operation needed, so dp[i][j] = dp[i-1][j-1]
• Otherwise: take the minimum among three possibilities — replacement (dp[i-1][j-1]), deletion (dp[i-1][j]), or insertion (dp[i][j-1]) — and add one step.

Initialization handles base cases where one string is empty:

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[][] dp = new int[len1 + 1][len2 + 1];

        // Initialize base cases
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i - 1][j - 1], dp[i - 1][j]),
                        dp[i][j - 1]
                    ) + 1;
                }
            }
        }

        return dp[len1][len2];
    }
}