ให้ลิสต์คำ words และสตริง letters หาความยาวคำที่ยาวที่สุดใน words ที่สร้างจาก letters ได้ (แต่ละตัวอักษรใช้ได้ครั้งเดียว)
ตัวอย่าง: words=["dog","cat","rat","bunny","lion","bat"], letters="gabctnyu" → 3 ("cat" หรือ "bat")
อัลกอริธึม
- นับความถี่ตัวอักษรใน letters (
ref) - สำหรับแต่ละคำ: นับความถี่ (
w) ถ้าทุกตัวอักษรใน w มีความถี่ ≤ ref → คำนี้สร้างได้ - เก็บความยาวสูงสุดของคำที่สร้างได้
การนำไปใช้
from collections import Counter
class Solution:
def solve(self, words, letters):
ref = Counter(letters)
max_len = 0
for word in words:
w = Counter(word)
if all(w[ch] <= ref[ch] for ch in w):
max_len = max(max_len, len(word))
return max_len
ob = Solution()
print(ob.solve(["dog","cat","rat","bunny","lion","bat"], "gabctnyu")) # 3
