Student Attendance Record II

Student Attendance Record II is a classic counting-DP problem. Instead of checking one record, we must count how many valid records of length n exist. The trick is to realize the validity of a record depends only on a tiny amount of state, so we can group billions of records into just six buckets.

The slow way first

The brute force is to generate all 3^n records and test each one. That is exponential and dies almost immediately — for n = 40 there are over 10^19 strings. We need something that scales linearly with n.

The question to ask: what do I actually need to know about a record so far to decide what I can append next? I do not need the whole string. I only need two facts: how many absences I have used (0 or 1) and how many late days are at the very end (0, 1, or 2). Everything else is irrelevant to the rules.

The idea: count by state

Track six counts, one per (absent, trailingLate) state where absent ∈ {0, 1} and trailingLate ∈ {0, 1, 2}. Start with the empty record: state (0, 0) holds the single empty string. Then for each of the n positions, push every count forward by deciding what character to append:

• Append P: absence unchanged, trailing late resets to 0.
• Append L: absence unchanged, trailing late goes up by one — but only from late < 2 (a 3-run is illegal).
• Append A: only from an absent = 0 state, moves it to absent = 1, trailing late resets to 0.

After processing all n characters, the answer is the sum of all six buckets — every record that survived without breaking a rule.

Walk through it

Step through the animation. The cells across the top place one concrete record character by character, while the six labels below show the count in every (absent, late) bucket. Watch how P dumps everything into the late-0 column, L shifts the late columns rightward, and A lifts a count from the top row into the bottom (absent) row.

Pseudocode

dp[absent][late] = number of valid records in that state
start: dp[0][0] = 1, everything else 0
repeat n times, building a fresh "new" grid each time:
    for every state (a, l):
        append P:  new[a][0]     += dp[a][l]     # late resets
    for every state (a, l) with l < 2:
        append L:  new[a][l + 1] += dp[a][l]     # late grows
    for every state (0, l):
        append A:  new[1][0]     += dp[0][l]      # use the one allowed absence
    take everything mod 1e9+7, then dp = new
answer = sum of all six dp buckets, mod 1e9+7

The Python solution

def checkRecord(n):
    MOD = 10**9 + 7
    dp = [[0, 0, 0], [0, 0, 0]]
    dp[0][0] = 1
    for _ in range(n):
        new = [[0, 0, 0], [0, 0, 0]]
        for a in range(2):
            for l in range(3):
                new[a][0] += dp[a][l]
        for a in range(2):
            for l in range(2):
                new[a][l + 1] += dp[a][l]
        new[1][0] += dp[0][0] + dp[0][1] + dp[0][2]
        for a in range(2):
            for l in range(3):
                new[a][l] %= MOD
        dp = new
    return sum(dp[a][l] for a in range(2) for l in range(3)) % MOD

• dp[a][l] is the number of valid records with a absences and l trailing late days. We seed dp[0][0] = 1 for the empty record.
• The P block routes every state into the late-0 column (new[a][0]), because a present day resets the late run.
• The L block shifts each state up one late level (new[a][l + 1]), and only runs for l < 2, so a 3rd consecutive L is never created.
• Line 13 is the A transition: only absent = 0 states may take an absence, and they all land in new[1][0] (absence used, late reset).
• We apply the modulus every round so the numbers never overflow, and line 19 sums all six buckets for the final count.

Complexity

We do a constant amount of work per character (just shuffling six numbers), so the whole thing is O(n) time and O(1) space. Collapsing an exponential space of strings into a handful of states is the heart of counting DP.

When this pattern shows up

Practice