Pythonで指定した文字を使って作成できる最長単語の長さを求めるプログラム

文字列のリスト words と、別の文字列 letters が与えられたとします。このとき、letters に含まれる文字だけを使って作成できる words 内の最も長い文字列の長さを求めます。どの単語も作成できない場合は 0 を返します。なお、同じ文字を再利用することはできません。

例として、words = ["dog", "cat", "rat", "bunny", "lion", "bat"]、letters = "gabctnyu" の場合を考えてみましょう。このとき出力は 3 になります。「cat」や「bat」なら与えられた文字で作成できますが、それより長い単語は作れないため、最大の長さは 3 となるからです。

解決のための手順

• ref := letters の各文字とその出現回数を格納したマップ（Counter）を作成する
• max_len := 0 で初期化する
• words 内の各 word について、以下を繰り返す：
  • w := word の各文字とその出現回数を格納したマップを作成する
  • l := word の長さ
  • counter := 0 で初期化する
  • w 内の各キー k について：
    • w[k] <= ref[k] であれば、counter を 1 増やす
    • そうでなければ、ループを抜ける
  • l > max_len かつ w のサイズが counter と等しい場合、max_len := l と更新する
• 最後に max_len を返す

より理解を深めるために、以下の実装例を見てみましょう。

サンプルコード

from collections import Counter
class Solution:
    def solve(self, words, letters):
        ref = Counter(letters)
        max_len = 0
        for word in words:
            w = Counter(word)
            l = len(word)
            counter = 0
            for k in w:
                if w[k] <= ref[k]:
                    counter += 1
                else:
                    break
            if l > max_len and len(w) == counter:
                max_len = l
        return max_len
ob = Solution()
words = ["dog", "cat", "rat", "bunny", "lion", "bat"]
letters = "gabctnyu"
print(ob.solve(words, letters))

入力

["dog", "cat", "rat", "bunny", "lion", "bat"], "gabctnyu"

出力

3

このアルゴリズムでは、Python 標準ライブラリの collections.Counter を活用することで、各文字の出現回数を簡単に比較できます。まず letters 全体の文字頻度を基準マップとして保持し、各単語ごとに必要な文字が十分に存在するかを確認します。すべての文字が条件を満たす単語のみを候補とし、その中で最も長いものの長さを結果として返します。計算量は単語数と各単語の文字数に依存するため、実用的な範囲で効率的に動作します。