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 <= 105This 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.
C++
Java
Python
C#
JavaScript
Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of n.
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays.
| 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. |
Student Attendance Record II - Leetcode 552 - Python • NeetCodeIO • 10,077 views views
Watch 9 more video solutions →Practice Student Attendance Record II with our built-in code editor and test cases.
Practice on FleetCode