Pythonで文字列の前半と後半が少なくとも1文字異なっているかどうかを判定する方法

小文字のみで構成された文字列が与えられたとき、その文字列を中央で分割して得られる2つの半分（前半と後半）の間に、少なくとも1文字の違いがあるかどうかを判定する問題を考えてみましょう。ここでの「違い」とは、含まれる文字が異なる場合もあれば、同じ文字でも出現回数（頻度）が異なる場合も含まれます。

また、文字列の長さが奇数の場合は、中央の1文字を無視し、残りの文字だけで前半と後半を比較します。

例えば、入力が s = "helloohekk" の場合を考えてみます。このとき前半は "hello"、後半は "ohekk" となり、両者は異なるため出力は True になります。

解決のアプローチ

この問題は、前半と後半それぞれの文字の出現頻度を数えて比較することで解決できます。具体的には以下の手順に従います。

• 前半用の頻度マップ left_freq を空のマップとして初期化する
• 後半用の頻度マップ right_freq を空のマップとして初期化する
• 文字列の長さを n とする
• インデックス 0 から n//2 - 1 までの各文字について、left_freq のカウントを1ずつ増やす
• インデックス n//2 から n - 1 までの各文字について、right_freq のカウントを1ずつ増やす
• 文字列内の各文字について、left_freq[char] と right_freq[char] が一致しない場合は True を返す
• すべての文字で頻度が一致していた場合は False を返す

実装例

以下のコードを見ると、処理の流れがより理解しやすくなります。

from collections import defaultdict
def solve(s):
    left_freq = defaultdict(int)
    right_freq = defaultdict(int)
    n = len(s)
    for i in range(n//2):
        left_freq[s[i]] += 1
    for i in range(n//2, n):
        right_freq[s[i]] += 1
    for char in s:
        if right_freq[char] != left_freq[char]:
            return True
    return False
s = "helloohekk"
print(solve(s))

入力

"helloohekk"

出力

True

コードのポイント

この実装では、Python標準ライブラリの defaultdict(int) を使うことで、存在しないキーにアクセスした際に自動的に0で初期化されるため、頻度カウントの処理を簡潔に書くことができます。

計算量については、文字列を一度走査して頻度を数え、再度走査して比較するため、全体の時間計算量は O(n)、必要な追加メモリは文字種に依存するため最大 O(26)（小文字アルファベットのみの場合）となります。これは非常に効率的なアプローチです。