Pythonで文字列の全文字が同じ頻度かどうかを確認する方法（1文字の削除を許可）

小文字のみで構成された文字列 s が与えられます。ここで、最大1文字だけ削除することで、すべての異なる文字の出現回数が等しくなる「有効な文字列」に変換できるかどうかを判定しましょう。

問題の例

入力が s = 'xyyzx' の場合を考えてみます。文字 z を1つ削除すると 'xyyx' になり、x と y の出現回数がどちらも2回で一致します。したがって、この場合の出力は True になります。

解法の考え方

まず各文字の出現回数を数え、その頻度が高々2種類にまとめられるかを確認します。3種類以上の異なる頻度が存在する場合は、1文字の削除では絶対に揃えられないため False を返します。具体的な手順は以下の通りです。

1. size := 26（アルファベットの種類数）とします。
2. occurrence: サイズ26の配列を用意し、文字列 s 内の各文字（a〜z）の出現頻度を格納します。
3. occr1 := 0、occr1_cnt := 0 で初期化します。
4. i を 0 から size-1 まで走査し、occurrence[i] が 0 でない最初の位置で、occr1 := occurrence[i]、occr1_cnt := 1 としてループを抜けます（第1の頻度グループの確定）。
5. occr2 := 0、occr2_cnt := 0 で初期化します。
6. j を i+1 から size-1 まで走査します。
   • occurrence[j] が occr1 と等しければ、occr1_cnt を +1 します。
   • 等しくなければ、そこを第2のグループとみなし、occr2_cnt := 1、occr := occurrence[j] としてループを抜けます。
7. k を j+1 から size-1 まで走査します。
   • occurrence[k] が occr1 と等しければ、occr1_cnt を +1 します。
   • occurrence[k] が occr2 と等しければ、occr2_cnt を +1 します。
   • どちらにも該当しなければ、3種類目の頻度が存在するということなので False を返します。
8. 最後に、occr1_cnt > 1 かつ occr2_cnt > 1 であれば、両方のグループから1文字ずつ削除する必要があるため False を返します。それ以外の場合は True を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

size = 26

def solve(s):
    # 各文字の出現回数をカウント
    occurrence = [0] * size
    for ch in s:
        occurrence[ord(ch) - ord('a')] += 1

    # 最初の頻度グループを見つける
    occr1 = 0
    occr1_cnt = 0
    for i in range(size):
        if occurrence[i] != 0:
            occr1 = occurrence[i]
            occr1_cnt = 1
            break

    # 第2の頻度グループを探す
    occr2 = 0
    occr2_cnt = 0
    for j in range(i + 1, size):
        if occurrence[j] != 0:
            if occurrence[j] == occr1:
                occr1_cnt += 1
            else:
                occr2_cnt = 1
                occr = occurrence[j]
                break

    # 残りの文字をチェック（3種類目の頻度がないか確認）
    for k in range(j + 1, size):
        if occurrence[k] != 0:
            if occurrence[k] == occr1:
                occr1_cnt += 1
            elif occurrence[k] == occr2:
                occr2_cnt += 1
            else:
                return False
        if occr1_cnt > 1 and occr2_cnt > 1:
            return False
    return True

s = 'xyyzx'
print(solve(s))

入力

'xyyzx'

出力

True

まとめ

このアルゴリズムは、各文字の出現頻度を一度数えた後、「頻度の種類が2種類以内に収まっているか」「両方のグループに複数の文字が属していないか」を確認するだけで答えを導き出せます。文字列の長さを n とすると、計算量は O(n + 26)、つまり事実上 O(n) であり、非常に効率的です。頻度のグループ分けというシンプルな発想で解ける、典型的な文字列操作の練習問題といえるでしょう。