Pythonで文字列内の各文字の出現頻度が、別の文字列の同じ文字の頻度の倍数または約数になっているかを判定する方法

2つの文字列 s と t が与えられたとき、s 内の各文字の出現回数が、t 内の同じ文字の出現回数の「倍数」または「約数（因数）」になっているかどうかを判定する問題を考えてみましょう。

問題の例

たとえば、入力が s = "xxyzzw"、t = "yyyxxxxzz" の場合、出力は True になります。その理由を見てみましょう。

• x: s では 2 回、t では 4 回出現 → 4 は 2 の倍数なので条件を満たす
• y: s では 1 回、t では 3 回出現 → 3 は 1 の倍数なので条件を満たす
• z: s でも t でも同じ回数出現 → 倍数・約数の関係にあるので条件を満たす
• w: s には 1 回あるが、t には存在しない → 比較対象がないためスキップされる

このようにすべての文字が条件を満たすため、結果は True となります。

解決のアプローチ

この問題は、以下の手順で解くことができます。

1. s_freq := 文字列 s に含まれるすべての文字とその出現頻度を格納したマップを作成する
2. t_freq := 文字列 t に含まれるすべての文字とその出現頻度を格納したマップを作成する
3. s_freq 内の各文字 ch について次を繰り返す
   • ch が t_freq に存在しない場合は、次の反復へ進む
   • t_freq[ch] が s_freq[ch] で割り切れる、または s_freq[ch] が t_freq[ch] で割り切れる場合は、次の反復へ進む
   • それ以外の場合は False を返す
4. すべてのチェックを通過したら True を返す

実装例

理解を深めるために、以下のPythonコードを実装してみましょう。

from collections import defaultdict
def solve(s, t):
    s_freq = defaultdict(int)
    t_freq = defaultdict(int)
    for i in range(0, len(s)):
        s_freq[s[i]] += 1
    for i in range(0, len(t)):
        t_freq[t[i]] += 1
    for ch in s_freq:
        if ch not in t_freq:
            continue
        if t_freq[ch] % s_freq[ch] == 0 or s_freq[ch] % t_freq[ch] == 0:
            continue
        else:
            return False
    return True
s = "xxyzzw"
t = "yyyxxxxzz"
print(solve(s, t))

入力

"xxyzzw", "yyyxxxxzz"

出力

True

補足：より簡潔な書き方

Pythonでは collections.Counter を使うことで、頻度マップの作成を1行で行うこともできます。

from collections import Counter
def solve(s, t):
    s_freq = Counter(s)
    t_freq = Counter(t)
    for ch, cnt in s_freq.items():
        if ch not in t_freq:
            continue
        if t_freq[ch] % cnt != 0 and cnt % t_freq[ch] != 0:
            return False
    return True

この実装では、割り切れない場合のみ False を返し、それ以外は最終的に True を返すというロジックを、より読みやすく表現しています。