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 <= 105The key to solving Student Attendance Record II is recognizing that we must count all valid attendance strings of length n while respecting two constraints: fewer than two A (absent) and no more than two consecutive L (late). This naturally leads to a Dynamic Programming formulation where the state tracks the current day, the number of absences used, and the number of consecutive lates.
Define DP states such as dp[i][a][l], representing the number of valid sequences of length i with a absences and l consecutive lates. For each step, we consider transitions by adding P (present), L, or A while maintaining the constraints. Since the number of absences can only be 0 or 1 and consecutive lates at most 2, the state space remains small.
The transitions accumulate counts modulo 10^9 + 7. The DP can be optimized to constant space by keeping only the previous day's states. This approach efficiently computes the total number of valid records for large n.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with State Tracking | O(n) | O(1) |
| DP with Full State Table | O(n) | O(n) |
NeetCodeIO
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.
Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of n.
1#include <stdio.h>
2#define MOD 1000000007
3
4int checkRecord(int n) {
5 int p_dp, a_dp,
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.
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.
Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of constrained sequence counting and dynamic programming problems like this appear in FAANG-style interviews. They test a candidate's ability to design efficient DP states and optimize space.
A dynamic programming table or a few state variables are sufficient for this problem. Since the constraints for absences and lates are small, you only need to track a limited number of DP states rather than large data structures.
The optimal approach uses dynamic programming to track the number of absences and consecutive lates at each step. By limiting the states to at most one absence and two consecutive lates, the solution runs in O(n) time with constant space optimization.
Dynamic programming works well because the number of valid attendance sequences for length n depends on smaller subproblems. Each day's decision builds upon previously computed states while enforcing the attendance constraints.
The JavaScript solution leverages arrays to conduct matrix operations, embracing matrix exponentiation to efficiently compute the number of valid attendance records.