Edit distance where a substitution only costs the first time This challenge is about the following variant of edit distance.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter x for a letter y only costs 1 the first time.  Any further substitutions of x for y cost 0.
As simple examples:
A = apppple
B = attttle

cost 1 (not 4) to transform A into B. This is because we change p for a t four times but we only charge for the first one.
A = apxpxple
B = atxyxtle

cost 2 (not 3) as the p to t substitution only costs 1 even though we do it twice.
A = apppple
B = altttte

cost 3. p -&gt; l costs 1. p -&gt; t costs 1 as does l -&gt; t.
If we assume the total length of the input is n, you must give the big O() of your algorithm. The best time complexity wins.

We should assume the alphabet size can be as large as n.
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...