String DP

Count the minimum number of single-character edits that turn word1 into word2. Three edits are allowed, each costing 1: insert a character, delete a character, or replace one character with another.

`word1`	`word2`	result	why
`"horse"`	`"ros"`	`3`	replace `h`→`r`, delete `r`, delete `e`
`"abc"`	`"abc"`	`0`	already equal
`""`	`"abc"`	`3`	insert all three characters

Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2. The answer is dp[word1.size()][word2.size()].

The base cases are where one side is empty: dp[i][0] = i (delete every remaining character) and dp[0][j] = j (insert every missing character).

For each pair of characters there are two cases.

If word1[i-1] == word2[j-1] the characters already line up, so nothing is spent: dp[i][j] = dp[i-1][j-1].

Otherwise pay 1 for the cheapest of the three edits, each of which is a smaller subproblem that is already solved:

delete word1[i-1] → dp[i-1][j]
insert word2[j-1] → dp[i][j-1]
replace word1[i-1] with word2[j-1] → dp[i-1][j-1]

C++

// Edit Distance (Levenshtein): the minimum number of single-character edits
// that turn word1 into word2. Allowed edits, each costing 1: insert a
// character, delete a character, replace one character with another.
int minDistance(const std::string& word1, const std::string& word2) {
    int m = word1.size(), n = word2.size();
    // dp[i][j] = edit distance between the first i characters of word1 and
    // the first j characters of word2.
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    // Base cases: one side is empty, so every remaining character is an edit.
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // delete all of word1
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // insert all of word2
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                // Characters already line up: nothing is spent here.
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Pay 1 for the cheapest of the three edits. Each option is a
                // smaller subproblem that has already been solved.
                dp[i][j] = 1 + std::min({dp[i - 1][j],     // delete word1[i-1]
                                         dp[i][j - 1],     // insert word2[j-1]
                                         dp[i - 1][j - 1]  // replace one with the other
                                        });
            }
        }
    }
    return dp[m][n];
}

Edit Distance (Levenshtein)

Longest Palindromic Substring