โปรแกรมหาความยาวของลำดับย่อยที่เป็นอนากรามมากที่สุดใน Python

สมมติว่าเรามีสตริงตัวพิมพ์เล็กสองตัวคือ S และ T เราต้องการหาความยาวของลำดับย่อยที่เป็นอนากราม (anagram subsequence) มากที่สุด

ตัวอย่างเช่น หาก S = "helloworld", T = "hellorld" ผลลัพธ์จะเป็น 8

ขั้นตอนการแก้ปัญหา

1. สร้างแมป c นับความถี่ตัวอักษรใน S
2. สร้างแมป d นับความถี่ตัวอักษรใน T
3. กำหนด res = 0
4. สำหรับแต่ละตัวอักษร ch ใน c:
   • หาก d[ch] > 0 ให้ res += min(c[ch], d[ch])
5. คืนค่า res

หมายเหตุ: ตัวอย่างในเอกสารต้นฉบับมี Output แสดงเป็น 1 ซึ่งอาจเป็นข้อผิดพลาด เนื่องจากตัวอักษรที่ซ้ำกันระหว่าง "helloworld" และ "hellorld" ได้แก่ h, e, l, l, o, r, l, d รวม 8 ตัวอักษร

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, a, b):
        c, d = {}, {}
        
        for ch in a:
            c[ch] = c.get(ch, 0) + 1
        
        for ch in b:
            d[ch] = d.get(ch, 0) + 1
        
        res = 0
        for ch in c:
            if d.get(ch, 0) > 0:
                res += min(c[ch], d[ch])
        
        return res

ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))  # Output: 8

อินพุต

S = "helloworld", T = "hellorld"

เอาต์พุต

8