"""Guided lab: score lesson alignment by LCS, then choose a 0/1 study plan."""


def common_topics(sequence, target):
    rows, cols = len(sequence), len(target)
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            if sequence[i - 1] == target[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j, matched = rows, cols, []
    while i and j:
        if sequence[i - 1] == target[j - 1]:
            matched.append(sequence[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(matched))


def study_plan(lessons, target, budget):
    """Lesson: (unique ID, positive minutes, topic-symbol string)."""
    if budget < 0 or any(minutes <= 0 for _, minutes, _ in lessons):
        raise ValueError("Budget must be nonnegative and lesson durations positive")
    if len({identity for identity, _, _ in lessons}) != len(lessons):
        raise ValueError("Lesson IDs must be distinct")
    matches = [common_topics(topics, target) for _, _, topics in lessons]
    dp = [[0] * (budget + 1) for _ in range(len(lessons) + 1)]
    for i, (_, minutes, _) in enumerate(lessons, 1):
        score = len(matches[i - 1])
        for remaining in range(budget + 1):
            dp[i][remaining] = dp[i - 1][remaining]
            if minutes <= remaining:
                dp[i][remaining] = max(dp[i][remaining],
                                       score + dp[i - 1][remaining - minutes])
    chosen, remaining = [], budget
    for i in range(len(lessons), 0, -1):
        # Equal scores choose the earlier row: skip the current lesson.
        if dp[i][remaining] != dp[i - 1][remaining]:
            chosen.append(i - 1)
            remaining -= lessons[i - 1][1]
    chosen.reverse()
    return {"chosen": [lessons[index][0] for index in chosen],
            "minutes": budget - remaining, "score": dp[-1][budget],
            "alignment": [{"id": lesson[0], "matched": match, "score": len(match)}
                          for lesson, match in zip(lessons, matches)]}