Pythonで指定された制約のもと、別の文字列から目的の文字列を生成できるか判定する方法

問題の概要

小文字のみで構成される2つの文字列 s と t が与えられたとします。このとき、次の制約条件に従って t を s から生成できるかどうかを判定するのが本記事の目的です。

制約条件

• 文字の一致： t に含まれる各文字は、s にも同じ個数だけ存在しなければなりません。たとえば、t に「a」が2つ含まれているなら、s にも「a」が2つ必要です。
• 前の文字による代替： t のある文字が s に存在しない場合は、その直前の2つの文字（ASCIIコードで1つ前と2つ前の文字）が s に存在するかを確認します。たとえば、「f」が t にはあるが s にはない場合、「d」と「e」を組み合わせて「f」を作ることができます。

たとえば、入力が s = "pghn"、t = "pin" の場合を考えてみましょう。「i」は s に直接存在しませんが、「g」と「h」を組み合わせて「i」を作ることができるため、出力は True になります。

解決のためのアルゴリズム

この問題は、文字の出現頻度を管理しながら順番に処理することで解決できます。手順は以下の通りです。

1. freq として、s 内の各文字の出現回数を記録します。
2. i を 0 から t の長さまで繰り返します。
   • freq[t[i]] が 0 以外の場合：freq[t[i]] を 1 減らします。
   • それ以外で、t[i] の1つ前の文字と2つ前の文字がどちらも freq に残っている場合：両方のカウントをそれぞれ 1 ずつ減らします。
   • 上記のいずれも満たさない場合：False を返します。
3. ループが最後まで完了すれば True を返します。

Pythonでの実装例

以下のコードでは、collections.defaultdict を使って文字頻度を効率的に管理しています。存在しないキーにアクセスしてもエラーにならず、デフォルト値 0 が返されるため、コードがシンプルになります。

from collections import defaultdict

def solve(s, t):
    freq = defaultdict(lambda: 0)
    # 文字列sの各文字の出現回数をカウント
    for i in range(0, len(s)):
        freq[s[i]] += 1
    # 文字列tの各文字について判定
    for i in range(0, len(t)):
        if freq[t[i]]:
            freq[t[i]] -= 1
        elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]):
            freq[chr(ord(t[i]) - 1)] -= 1
            freq[chr(ord(t[i]) - 2)] -= 1
        else:
            return False
    return True

s = "pghn"
t = "pin"
print(solve(s, t))

入力

"pghn", "pin"

出力

True

処理のポイント

• ord() 関数で文字をASCIIコード（整数）に変換し、1つ前・2つ前の文字を求めた後、chr() で再び文字に戻しています。
• defaultdict(lambda: 0) を使うことで、未登録の文字に対する参照でも安全に 0 が返され、条件分岐が簡潔になります。
• 計算量は文字列の長さに比例する O(n + m)（n は s の長さ、m は t の長さ）となり、非常に効率的です。