Pythonで文字列から作れる「pizza」の個数を数えるプログラム

問題概要

小文字のみで構成された文字列 s が与えられたとき、その中に含まれる文字を使って、何個の「pizza」という文字列を作ることができるかを求める問題です。

文字は任意の順序で使用できますが、同じ文字を複数回使うことはできません(ある「pizza」を作るために使った文字は、別の「pizza」には使えません)。

例えば、入力が "ihzapezlzzilaop" の場合、出力は 2 になります。

• 「pizza」1個を作るのに必要な文字:p × 1、i × 1、z × 2、a × 1
• この文字列には p が2個、i が2個、z が3個、a が2個含まれているため、最大2個の「pizza」が作れます。

解き方のアプローチ

この問題は非常にシンプルで、以下の手順で解くことができます。

1. s 内に 'p' が出現する回数(p_freq)を数える
2. s 内に 'i' が出現する回数(i_freq)を数える
3. s 内に 'z' が出現する回数(z_freq)を数える(「pizza」1個につき z が2個必要なので、後ほど 2 で割る)
4. s 内に 'a' が出現する回数(a_freq)を数える
5. p_freq、i_freq、z_freq // 2、a_freq の最小値を返す

最小値を取る理由は、「pizza」を1個作るためには4種類すべての文字が揃う必要があるからです。どれか1つの文字でも不足していれば、それ以上「pizza」を作ることはできません。

実装例(Python)

class Solution:
    def solve(self, s):
        p_freq = s.count('p')
        i_freq = s.count('i')
        z_freq = s.count('z')
        a_freq = s.count('a')
        return min(p_freq, i_freq, z_freq // 2, a_freq)

ob = Solution()
print(ob.solve("ihzapezlzzilaop"))

入力

"ihzapezlzzilaop"

出力

2

コードのポイント

• str.count() メソッドを使えば、特定の文字の出現回数を簡単に取得できます。
• 'z' は「pizza」1個あたり2個必要なため、整数除算 z_freq // 2 で作成可能な個数を計算します。
• min() 関数で4つの値の最小値を取ることで、作れる「pizza」の最大個数が求まります。

時間計算量は O(n)(n は文字列の長さ)、空間計算量は O(1) であり、非常に効率的な解法と言えます。