ให้สตริง s และ t ความยาวเท่ากัน แบ่งเป็น substring คู่ๆ ที่มีขนาดเท่ากันและเป็น anagram หาจุดตัดที่ให้จำนวน partition มากที่สุด
ตัวอย่าง: s="bowcattiger", t="owbactietgr" → [0,3,5,6,10] (5 partitions: bow/owb, ca/ac, t/t, tige/ietg, r/r)
อัลกอริธึม
- นับความถี่ตัวอักษรของทั้งสองสตริง (
ca,cb) - ถ้าความถี่รวมไม่เท่ากัน → ไม่มีคำตอบ
- เดินจากขวาไปซ้าย: ลดความถี่ตัวอักษรที่ผ่านไป ถ้า
ca == cb→ จุดตัดที่นั่น - เรียงจุดตัดจากน้อยไปมาก
การนำไปใช้
from collections import Counter
class Solution:
def solve(self, a, b):
intervals = []
ca = Counter(a)
cb = Counter(b)
if ca != cb:
return []
for x in reversed(range(len(a))):
ca[a[x]] -= 1
cb[b[x]] -= 1
if ca == cb:
intervals.append(x)
return sorted(intervals)
ob = Solution()
print(ob.solve("bowcattiger", "owbactietgr")) # [0, 3, 5, 6, 10]
