Problem statement

https://binarysearch.com/problems/Swap-Characters-Once-to-Minimize-Differences/

Solution

The idea is if we have d answer for original strings, than we can have d, d - 1 or d - 2.

  1. We have d - 2, if among pairs zip(s, t) exist two pairs (x, y) and (y, x).
  2. We have d if consider set of the first elements in zip(s, t) and set of the second elements do not intersect.
  3. We have d - 1 in the opposite case.

Complexity

It is O(n) for time and O(min(n, m^2)) for space, where m = 26 is the size of alphabet.

Code

class Solution:
    def solve(self, s, t):
        n = len(s)
        base = sum(x == y for x, y in zip(s, t))
        pairs = set([(x, y) for x, y in zip(s, t) if x != y])
        if any((y, x) in pairs for x, y in pairs):
            addon = 2
        elif not set(x for x, _ in pairs) & set(y for _, y in pairs):
            addon = 0
        else:
            addon = 1

        return n - base - addon