Introduction

“Change strings to make them equal” is not one algorithmic problem. It is a family of problems whose answer depends on the allowed operations. If you are allowed only replacement, the solution is simple. If insertion and deletion are allowed too, you need edit distance.

Start by Defining the Operation Model

Before writing code, answer one question: what counts as one change?

Common versions are:

• replace one character
• insert one character
• delete one character
• swap adjacent characters
• use weighted costs instead of cost 1

If you skip this step, it is easy to build an algorithm that is correct for the wrong problem.

For example, with equal-length strings and replacement only, "abc" to "axc" needs one change. If insertions and deletions are allowed, the same answer happens to be one, but that is not always true for longer examples.

Equal-Length Strings With Replacement Only

If the strings have the same length and replacement is the only operation, count mismatched positions.

1def min_replacements(a: str, b: str) -> int:
2    if len(a) != len(b):
3        raise ValueError("strings must have equal length")
4
5    changes = 0
6    for left, right in zip(a, b):
7        if left != right:
8            changes += 1
9    return changes
10
11
12print(min_replacements("abcde", "abzxy"))

This runs in O(n) time and O(1) extra space. It is the right answer for many interview questions that look more complex than they actually are.

A shorter version using a generator is fine too:

1def min_replacements_compact(a: str, b: str) -> int:
2    if len(a) != len(b):
3        raise ValueError("strings must have equal length")
4    return sum(1 for x, y in zip(a, b) if x != y)

General String Changes With Edit Distance

If insertions, deletions, and substitutions are allowed, the standard solution is Levenshtein distance. Dynamic programming works because each prefix pair depends on smaller prefix pairs.

1def edit_distance(a: str, b: str) -> int:
2    rows = len(a) + 1
3    cols = len(b) + 1
4    dp = [[0] * cols for _ in range(rows)]
5
6    for i in range(rows):
7        dp[i][0] = i
8    for j in range(cols):
9        dp[0][j] = j
10
11    for i in range(1, rows):
12        for j in range(1, cols):
13            cost = 0 if a[i - 1] == b[j - 1] else 1
14            dp[i][j] = min(
15                dp[i - 1][j] + 1,
16                dp[i][j - 1] + 1,
17                dp[i - 1][j - 1] + cost,
18            )
19
20    return dp[-1][-1]
21
22
23print(edit_distance("kitten", "sitting"))

This solution is O(n * m) in time and space for string lengths n and m.

Space Optimization for Large Inputs

If the strings are long, the full matrix may be unnecessarily expensive. You only need the previous row and the current row at any step.

1def edit_distance_optimized(a: str, b: str) -> int:
2    if len(a) < len(b):
3        a, b = b, a
4
5    prev = list(range(len(b) + 1))
6
7    for i, ca in enumerate(a, start=1):
8        curr = [i] + [0] * len(b)
9        for j, cb in enumerate(b, start=1):
10            cost = 0 if ca == cb else 1
11            curr[j] = min(
12                curr[j - 1] + 1,
13                prev[j] + 1,
14                prev[j - 1] + cost,
15            )
16        prev = curr
17
18    return prev[-1]

This still takes O(n * m) time but uses much less memory.

Choose the Right Algorithm for the Real Task

Many production use cases are not exactly Levenshtein distance either. Spell-checking, entity matching, and typo correction often need a mix of heuristics, normalization, and search pruning before distance is even computed.

For example, if case differences should not count, normalize first:

left = "ServerError".lower()
right = "servererror".lower()
print(edit_distance(left, right))

If adjacent swaps should count as one operation, standard Levenshtein is not enough and Damerau-Levenshtein is closer to the intended model.

Common Pitfalls

A common mistake is using mismatch counting when strings have different lengths. That only solves the replacement-only equal-length case.

Another mistake is solving a simple replacement problem with full dynamic programming. The answer is correct, but the solution is slower and less clear than necessary.

It is also easy to forget edge cases such as empty strings, identical inputs, or normalization requirements for case and whitespace.

Summary

• The right algorithm depends entirely on which edits are allowed.
• For equal-length replacement-only problems, count mismatched positions.
• For insertion, deletion, and substitution, use Levenshtein distance.
• Space-optimized dynamic programming is useful for long strings.
• Define the rules first, or you may solve the wrong problem correctly.