Watch 10 video solutions for Student Attendance Record II, a hard level problem involving Dynamic Programming. This walkthrough by NeetCodeIO has 11,459 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:
'A': Absent.'L': Late.'P': Present.Any student is eligible for an attendance award if they meet both of the following criteria:
'A') for strictly fewer than 2 days total.'L') for 3 or more consecutive days.Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7.
Example 1:
Input: n = 2 Output: 8 Explanation: There are 8 records with length 2 that are eligible for an award: "PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL" Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).
Example 2:
Input: n = 1 Output: 3
Example 3:
Input: n = 10101 Output: 183236316
Constraints:
1 <= n <= 105Problem Overview: Count the number of valid attendance strings of length n using characters 'A' (Absent), 'L' (Late), and 'P' (Present). A record is valid if it contains fewer than two 'A' characters and never has three consecutive 'L'. Return the total count modulo 1e9+7.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Model the constraints directly with DP states. Track three pieces of information while building the string: the current length i, how many absences have been used (0 or 1), and the number of trailing 'L' characters (0–2). For each state, append 'P', 'A', or 'L' if the constraints allow it. The transitions update the absence count and reset or extend the late streak. This produces at most n * 2 * 3 states, so the runtime is O(n) with O(n) memory (or O(1) using rolling arrays). This approach clearly expresses the constraints and is the most common solution using dynamic programming.
Approach 2: Mathematical Matrix Exponentiation (O(log n) time, O(1) space)
The DP transitions form a linear recurrence between states. Instead of iterating day by day, represent the transitions between the six possible states (A ∈ {0,1} and L ∈ {0,1,2}) as a transition matrix. Multiplying this matrix advances the state by one day. Raising the matrix to the power n using fast exponentiation computes the result in O(log n) time. This converts the iterative DP into a mathematical recurrence solved with matrix exponentiation. Space stays O(1) because the matrix size is constant.
Recommended for interviews: The dynamic programming solution is what most interviewers expect. It demonstrates that you can translate constraints into states and transitions. The matrix exponentiation optimization is valuable for very large n and shows deeper knowledge of recurrence relations and DP optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Tracking) | O(n) | O(n) or O(1) | Best general solution. Easy to reason about constraints and typical interview expectation. |
| Matrix Exponentiation | O(log n) | O(1) | Useful when n is extremely large or when optimizing DP recurrences with fixed states. |