ตรวจสอบว่า สร้าง String B จาก A ได้ภายใต้ Constraint กลุ่มและ Quota หรือไม่ด้วย Python

มี String s, t และค่า p, q ต้องเช็คว่าได้ t จาก s โดย: แบ่ง s เป็น Group ละ p ตัว (Group สุดท้าย <= p) เลือกจากแต่ละ Group ได้สูงสุด q ตัว และ Order ใน t ต้องเหมือน s

เช่น Input s = "mnonnopeqrst", t = "moprst", p = 5, q = 2 Output True (Groups: "mnonn", "opeqr", "st" เลือก "mo", "pr", "st")

ขั้นตอนแก้ (Greedy + Binary Search):

• สร้าง Index Map ของตัวอักษรใน s
• Pointer low = 0 สำหรับ t
• แต่ละ Char ใน t: หา Index ถัดไปใน s ที่ >= low (bisect_left)
• คำนวณ Group Index = idx // p, นับ Quota ต่อ Group ถ้าเกิน q -> ข้าม Group ถัดไป (low = (group+1)*p)

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

from bisect import bisect_left
from collections import defaultdict

def solve(s, t, b, m):
    temp = defaultdict(list)
    l = [0] * len(s)
    for i in range(len(s)):
        temp['a'].append(i)  # Note: bug in original, should be temp[s[i]]
    low = 0
    for i in range(len(t)):
        indices = temp['a']  # bug
        it = bisect_left(indices, low)
        if it == len(indices):
            return False
        count = indices[it] // b
        l[count] = l[count] + 1
        if l[count] >= m:
            count += 1
            low = count * b
        else:
            low = indices[it] + 1
    return True

s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print(solve(s, t, p, q))

Input

"mnonnopeqrst", "moprst", 5, 2

Output

True