【Python】2つの文字列を一致させるために必要な前処理の最小移動回数を求める方法

問題の概要

同じ長さを持ち、小文字の英字のみからなる2つの文字列 P と Q が与えられます。次に示す操作を適用した後、P を Q と完全に一致させるために、事前に P に施すべき前処理（文字の置き換え）の最小回数を求めます。

• 任意のインデックス i を選び、文字 p[i] と q[i] を入れ替える。
• 任意のインデックス i を選び、文字 p[i] と p[n − i − 1] を入れ替える。
• 任意のインデックス i を選び、文字 q[i] と q[n − i − 1] を入れ替える。

注： インデックス i の範囲は 0 ≤ i < n です。

また、1回の前処理では、P 内の任意の1文字を英語アルファベットの別の文字へ変更することができます。

たとえば、入力が P = "pqprpqp"、Q = "qprpqpp" の場合、答えは 4 になります。P0 = 'q'、P2 = 'r'、P3 = 'p'、P4 = 'q' と置き換えると P は "qqrpqqp" となり、その後 swap(P1, Q1)、swap(P1, P5) の順に操作を実行することで、両方の文字列を一致させることができます。

解き方のアプローチ

この問題は、対称的な位置関係にあるペア（i と n − i − 1）ごとに登場する文字の種類をマップで管理し、その種類数に応じて必要な前処理回数を加算していくことで解けます。具体的な手順は以下の通りです。

• n := 文字列 P の長さとする。
• res := 0 で初期化する。
• i を 0 から n / 2 の範囲で繰り返す。
  • my_map := 新しいマップを作成し、my_map[P[i]] := 1 とする。
  • P[i] が P[n − i − 1] と等しい場合、my_map[P[n − i − 1]] を +1 する。
  • Q[i] が my_map に存在すれば my_map[Q[i]] を +1、存在しなければ my_map[Q[i]] := 1 とする。
  • Q[n − i − 1] が my_map に存在すれば my_map[Q[n − 1 − i]] を +1、存在しなければ my_map[Q[n − 1 − i]] := 1 とする。
  • size := my_map の要素数とする。
  • size が 4 の場合：res に 2 を加算する。
  • size が 3 の場合：res に 1 +（P[i] と P[n − i − 1] が等しければ 1、そうでなければ 0）を加算する。
  • size が 2 の場合：my_map[P[i]] が 2 でなければ res に 1 を加算する。
• n が奇数であり、かつ P[n / 2] が Q[n / 2] と異なる場合、res に 1 を加算する。
• 最後に res を返す。

実装例

理解を深めるために、Pythonでの実装例を見てみましょう。

def count_preprocess(P, Q):
    n = len(P)
    res = 0
    for i in range(n // 2):
        my_map = dict()
        my_map[P[i]] = 1
        if P[i] == P[n - i - 1]:
            my_map[P[n - i - 1]] += 1
        if Q[i] in my_map:
            my_map[Q[i]] += 1
        else:
            my_map[Q[i]] = 1
        if Q[n - i - 1] in my_map:
            my_map[Q[n - 1 - i]] += 1
        else:
            my_map[Q[n - 1 - i]] = 1
        size = len(my_map)
        if (size == 4):
            res += 2
        elif (size == 3):
            res += 1 + (P[i] == P[n - i - 1])
        elif (size == 2):
            res += my_map[P[i]] != 2
    if (n % 2 == 1 and P[n // 2] != Q[n // 2]):
        res += 1
    return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

入力

"pqprpqp", "qprpqpp"

出力

4