Edit distance where a substitution only costs the first time
Naive recursive algorithm \$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \$
The basic idea is try adding, removing and replacing one character and recursive.

def f(str1, str2):
  l1, l2 = len(str1), len(str2)
  mapping = set()
  def g(p1, p2):
    if l1 == p1 or l2 == p2:
      return l1 + l2 - p1 - p2
    cost1 = g(p1 + 1, p2) + 1
    cost2 = g(p1, p2 + 1) + 1
    if str1[p1] != str2[p2] and (str1[p1], str2[p2]) not in mapping:
      mapping.add((str1[p1], str2[p2]))
      cost3 = g(p1 + 1, p2 + 1) + 1
      mapping.discard((str1[p1], str2[p2]))
    else:
      cost3 = g(p1 + 1, p2 + 1)
    return min(cost1, cost2, cost3)
  return g(0, 0)

The function g will be invoked \$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \$ times[1]. While adding, discarding, or checking an element in the mapping cost \$ O(1) \$ on average.
[1]: Based on https://oeis.org/A027618 ; I don't know why actually...