Is Student Attendance Record II easy or hard?

LeetCode classifies this problem as Hard because it requires modeling multiple constraints simultaneously. The difficulty comes from defining correct DP states and transitions, and recognizing that the recurrence can also be optimized using matrix exponentiation.

Student Attendance Record II Python/Java solution

Python and Java implementations typically use a 3D DP state: day index, absence count (0 or 1), and consecutive L count (0–2). Each iteration updates the states using modular arithmetic with 1e9+7. The same logic translates directly across Python, Java, C++, and other languages.

How to solve Student Attendance Record II in O(n)?

Use DP with states representing (absences used, consecutive L count). For each position, append 'P', 'A', or 'L' if valid. 'P' resets the late streak, 'A' increments absence count if it is still zero, and 'L' increases the late streak up to two. Summing all valid states after n steps gives the answer.

What is the best approach for Student Attendance Record II?

Dynamic Programming with state tracking is the most practical solution. Track the number of absences used (0 or 1) and the number of trailing L characters (0–2) while iterating through the days. This creates only six states per day, giving O(n) time complexity and O(1) or O(n) space.

Is Student Attendance Record II asked at Google/Amazon/Meta?

Variants of constrained sequence counting and DP state transition problems appear in interviews at companies like Google, Amazon, and Meta. This problem tests dynamic programming modeling, state compression, and sometimes mathematical optimization using matrix exponentiation.

What data structure is used in Student Attendance Record II?

The core structure is a dynamic programming table or a few rolling arrays representing the six possible states. In the optimized solution, a fixed-size matrix is used to represent state transitions for fast exponentiation.

What is the time complexity of Student Attendance Record II?

The standard dynamic programming solution runs in O(n) time because each day updates a constant number of states (six). A matrix exponentiation optimization reduces the complexity to O(log n) by exponentiating a fixed transition matrix.

Description Solution Video 27:10

552. Student Attendance Record II

Hard57.1% acceptance3 companies

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 10⁹ + 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: