Kiểm tra tạo chuỗi B từ A với ràng buộc nhóm và giới hạn chọn (Python)

Bài toán: Cho chuỗi s, t và tham số p, q. Chia s thành các nhóm p ký tự (nhóm cuối ≤ p). Từ mỗi nhóm chọn tối đa q ký tự (giữ thứ tự). Kiểm tra có tạo được t không.

Thuật toán Greedy + Binary Search

Duyệt t, với mỗi ký tự tìm vị trí sớm nhất trong s thỏa mãn ràng buộc nhóm.

Triển khai Python

from bisect import bisect_left
from collections import defaultdict

def solve(s, t, b, m):
    # b = p (group size), m = q (max pick per group)
    pos_map = defaultdict(list)
    for i, ch in enumerate(s):
        pos_map[ch].append(i)
    
    low = 0  # vị trí nhỏ nhất cho phép trong s
    group_picks = [0] * len(s)  # số lượng đã chọn từ mỗi group
    
    for ch in t:
        indices = pos_map[ch]
        # Tìm index đầu tiên ≥ low
        idx = bisect_left(indices, low)
        if idx == len(indices):
            return False
        
        pos = indices[idx]
        group_idx = pos // b
        group_picks[group_idx] += 1
        
        if group_picks[group_idx] >= m:
            # Group này đã chọn đủ q ký tự, buộc phải sang group sau
            low = (group_idx + 1) * b
        else:
            # Còn chọn được trong group này, tiếp từ vị trí sau
            low = pos + 1
    
    return True

# Test
print(solve("mnonnopeqrst", "moprst", 5, 2))  # True
# Groups: "mnonn" "opeqr" "st"
# Pick: m,o from group0 (2 chars), p,r from group1 (2 chars), s,t from group2
print(solve("abc", "abc", 2, 1))              # False: group0="ab" pick 1, group1="c" pick 1, but need 3 chars

Kết quả

True

Giải thích

• pos_map lưu vị trí của mỗi ký tự trong s.
• bisect_left tìm vị trí sớm nhất ≥ low.
• group_idx = pos // b xác định nhóm của vị trí.
• group_picks đếm số đã chọn từ mỗi nhóm.
• Khi nhóm đạt giới hạn m, low nhảy đến đầu nhóm sau.
• Độ phức tạp: O(|t| log |s|) time, O(|s|) space.