Student Attendance Record II (LeetCode 552)

The problem

An attendance record is a string of P (present), A (absent) and L (late). A record earns an award if it has fewer than 2 As in total and never 3 or more Ls in a row. Given n, count the award-eligible records of length n, modulo 10⁹ + 7.

Input:  n = 2
Output: 8

Of the 9 two-letter records, only AA fails (two absences). The other 8 are fine.

How to think about it

Start with brute force. Generate all 3ⁿ strings and check each. For n = 10 that’s 59,049; for n = 100,000 it’s absurd.

The key insight: to decide whether the next letter is allowed, you only need two facts. How many As so far (0 or 1), and how many Ls the string currently ends with (0, 1 or 2). The rest of the string’s history is irrelevant. So the state is (day, absences, trailing_lates), and there are only n × 2 × 3 states.

Write each choice as a state change.

• P: absences stay, trailing lates reset to 0.
• A: absences go up by 1, trailing lates reset to 0.
• L: absences stay, trailing lates go up by 1.

If a move makes absences 2 or trailing lates 3, that branch is dead and contributes 0. If you’ve filled all n days without dying, that’s one valid record.

Which pattern is this? Counting DP. The tell is “count strings with local rules”: put exactly the facts the rules need into the state, and the rest of the recurrence writes itself.

Approach

1. Define dp(i, a, l): the number of ways to fill days i..n-1, given a absences so far and l trailing lates.
2. If a == 2 or l == 3, the record already broke a rule: return 0.
3. If i == n, the record is complete and valid: return 1.
4. Otherwise sum the three choices: dp(i+1, a, 0) for P, dp(i+1, a+1, 0) for A, dp(i+1, a, l+1) for L. Take mod 10⁹ + 7.
5. Memoise and return dp(0, 0, 0).

Solution

from functools import lru_cache
def checkRecord(n):
    MOD = 10**9 + 7
    @lru_cache(None)
    def dp(i, a, l):
        if a == 2 or l == 3: return 0       # broke a rule
        if i == n: return 1                 # complete, valid record
        return (dp(i + 1, a, 0)          # present
                + dp(i + 1, a + 1, 0)    # absent
                + dp(i + 1, a, l + 1)) % MOD  # late
    return dp(0, 0, 0)
# checkRecord(2) -> 8

Alternative: bottom-up (handles n = 100,000)

The memoised version recurses n levels deep, so Python’s recursion limit breaks it long before LeetCode’s n = 100,000. The same six states can be rolled forward one day at a time instead. dp[a][l] counts valid records so far with a absences and l trailing lates:

def checkRecord(n):
    MOD = 10**9 + 7
    dp = [[1, 0, 0], [0, 0, 0]]          # empty record: a=0, l=0
    for _ in range(n):
        new = [[0, 0, 0], [0, 0, 0]]
        for a in range(2):
            for l in range(3):
                c = dp[a][l]
                if not c: continue
                new[a][0] = (new[a][0] + c) % MOD              # P: trailing lates reset
                if a == 0:
                    new[1][0] = (new[1][0] + c) % MOD          # A: one absence used
                if l < 2:
                    new[a][l + 1] = (new[a][l + 1] + c) % MOD  # L: one more late
        dp = new
    return sum(map(sum, dp)) % MOD
# checkRecord(2) -> 8, checkRecord(10101) -> 183236316

Same O(n) time, but O(1) space and no recursion. This is the version to submit. It matches the memoised one for every n from 1 to 59, and runs n = 100,000 in about 0.15 s.

Dry run

For n = 2, the states that matter on day 1 (one letter already placed), and day 0:

The memo held 10 states with 7 cache hits for n = 2. The code also gives 3 for n = 1, 19 for n = 3 and 3536 for n = 10.

Complexity

• Time: O(n). There are n × 2 × 3 live states, each doing O(1) work.
• Space: O(n). For the memo and the recursion stack, which is n deep.

Edge cases and pitfalls

• Recursion depth. LeetCode allows n up to 100,000, and this recursion goes n levels deep. With Python’s default limit of 1000 it raises RecursionError already at n = 1000 (we checked: 900 works, 1000 fails). In an interview, convert to a bottom-up loop over days with 6 counters, which is also O(1) space.
• “Trailing” lates, not total lates. LLPLL is fine; only three in a row are banned. A P or A must reset l to 0.
• Checking the death condition after i == n would accept records that end in a violation. Check it first, as the code does.
• Forgetting the modulus on the sum lets numbers grow huge (slow in Python, overflow elsewhere).

Related problems

• Count Vowels Permutation (LeetCode 1220): counting DP whose state is just the last letter.
• Decode Ways (LeetCode 91): count strings with local validity rules.
• Climbing Stairs (LeetCode 70): the base counting recurrence.