⚡Flashcard Drill➔
NeetCode #707LC-552Hard1-D Dynamic Programming
← Back to All Problems

#707 · #552 · Student Attendance Record II(学生出勤记录 II)

📌 Problem Statement & Constraints

Count the number of attendance records of length n (each day is A absent, L late, or P present) that contain at most one A and no three consecutive L, modulo 10^9 + 7. Constraints: 1 <= n <= 10^5.

💡 Core Algorithmic Approaches

  1. Track two dimensions of state: how many A have been used (0 or 1) and the length of the current trailing run of L (0, 1, or 2).
  2. Appending P resets the trailing run to 0; appending L increments it (allowed only while it stays below 2); appending A resets the run and is allowed only when no A has been used.
  3. Roll a 2x3 table forward one day at a time, keeping constant work per day.
  4. The answer is the sum over all six states after n days.

💻 Benchmark Python3 Implementation

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        # dp[a][l]: a = number of A used (0 or 1), l = trailing L count (0,1,2)
        dp = [[0] * 3 for _ in range(2)]
        dp[0][0] = 1                   # empty record
        for _ in range(n):
            ndp = [[0] * 3 for _ in range(2)]
            for a in range(2):
                for l in range(3):
                    v = dp[a][l]
                    if not v:
                        continue
                    ndp[a][0] = (ndp[a][0] + v) % MOD            # append P
                    if a == 0:
                        ndp[1][0] = (ndp[1][0] + v) % MOD        # append A
                    if l < 2:
                        ndp[a][l + 1] = (ndp[a][l + 1] + v) % MOD  # append L
            dp = ndp
        return sum(dp[a][l] for a in range(2) for l in range(3)) % MOD

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): constant work per day across six states.
💾 Space Complexity
O(1): two 2x3 tables.

⚠️ Interview Pitfalls & Follow-ups

  • Allowing two or more As: the absent count is capped at one, which the a dimension enforces.
  • Tracking only the last character: three consecutive Ls must be excluded, so the trailing-L run length is part of the state.
  • Seeding dp[0][0] = 1 incorrectly: the empty record has zero As and zero trailing Ls.
  • Summing only the no-A states: records with exactly one A also count, so all six states are summed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems