โปรแกรมนับจำนวนสตริงสูงสุดที่เราสร้างได้จากรายการคำและจำนวนตัวอักษรใน python

สมมติว่าเรามีรายการสตริงที่แต่ละสตริงประกอบด้วยตัวอักษร "A" และ "B" สองตัว เรามีสองค่า a และ b เราต้องหาจำนวนสตริงสูงสุดที่สามารถสร้างได้ เราสามารถใช้ "A" ได้ไม่เกินจำนวนและ "B" สูงสุดจำนวน b โดยไม่ต้องใช้ซ้ำ

ดังนั้น ถ้าอินพุตเหมือน strings =["AAABB", "AABB", "AA", "BB"] a =4 b =2 เอาต์พุตจะเป็น 2 เนื่องจากเราสามารถหาสตริงได้โดยใช้ 4 "A "s และ 2 "B"s ["AABB","AA"].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• คู่ :=รายการใหม่
• สำหรับแต่ละ w ในสตริง ทำ
  • A :=จำนวน "A" ใน w
  • B :=ขนาด w - A
  • ใส่คู่ (A, B) ที่ส่วนท้ายของคู่
• ans :=แผนที่ที่ (a, b) มีค่า 0
• สำหรับแต่ละ pait (A, B) เป็นคู่ ทำ
  • temp :=แผนที่ใหม่จาก ans
  • สำหรับแต่ละคู่ (temp_a, temp_b) และค่า wc ของ ans ทำ
    • ถ้า temp_a>=A และ temp_b>=B แล้ว
      • rem :=a pait (temp_a - A, temp_b - B)
      • temp[rem] :=สูงสุดของ temp[rem] (หากไม่มี rem อยู่ 0) และ (wc + 1)
    • ตอบ :=ชั่วคราว
• คืนค่าสูงสุดของรายการค่าทั้งหมดของ ans

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, strings, a, b):
      pairs = []
      for w in strings:
         A = w.count("A")
         B = len(w) - A
         pairs.append((A, B))
      ans = {(a, b): 0}
      for A, B in pairs:
         temp = dict(ans)
         for (temp_a, temp_b), wc in ans.items():
            if temp_a >= A and temp_b >= B:
               rem = (temp_a - A, temp_b - B)
               temp[rem] = max(temp.get(rem, 0), wc + 1)
         ans = temp
      return max(ans.values())

ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))

อินพุต

["AAABB", "AABB", "AA", "BB"], 4, 2

ผลลัพธ์

2