Student Attendance Record II - Solution & Explanation
Problem Statement
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:
- The student was absent (
'A') for strictly fewer than 2 days total. - The student was never late (
'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 <= 105
Approach Overview
Problem 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 1: Dynamic Programming Approach
This approach leverages dynamic programming to count eligible attendance records. We define a function dp[i][a][l], which represents the number of valid sequences of length i with a absences and l consecutive lates. The transitions will account for adding 'P', 'A', or 'L' to existing records, ensuring we respect the problem's constraints.
The C solution uses a bottom-up dynamic programming approach with space optimization. Arrays l_dp track sequences ending in late days to limit space, and the solution iteratively calculates valid sequences of increasing length up to n.
Complexity
Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of n.
Approach 2: Mathematical Matrix Exponentiation Approach
This approach uses matrix exponentiation to efficiently solve the problem by leveraging the recursive relationship of the transformation matrices, which model the state transitions of the sequences. The matrix exponentiation technique drastically reduces the time complexity by harnessing fast exponentiation properties.
The C code uses matrix exponentiation to compute the count of valid sequences. The matrices model possible state transitions, and raising the transition matrix to the nth power efficiently computes the number of valid sequences.
Complexity
Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of |
| Mathematical Matrix Exponentiation Approach | Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Student Attendance Record II - Leetcode 552 - Python • NeetCodeIO • 11,733 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Student Attendance Record II easy or hard?
Student Attendance Record II Python/Java solution
How to solve Student Attendance Record II in O(n)?
What is the best approach for Student Attendance Record II?
Is Student Attendance Record II asked at Google/Amazon/Meta?
What data structure is used in Student Attendance Record II?
What is the time complexity of Student Attendance Record II?
Ready to solve this problem?
Practice Student Attendance Record II with our built-in code editor and test cases.
Practice on FleetCode