Algorithm
Problem Name: 552. Student Attendance Record II
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const checkRecord = function(n) {
let P = 1
let L1 = 1
let L2 = 0
let A = 1
let pureP = 1
let pureL1 = 1
let pureL2 = 0
const mod = 10 ** 9 + 7
for (let i = 2; i < n + 1; i++) {
const newP = (P + L1 + L2 + A) % mod
const newL1 = (P + A) % mod
const newL2 = L1
const newA = (pureP + pureL1 + pureL2) % mod
P = newP
L1 = newL1
L2 = newL2
A = newA
const newPureP = (pureP + pureL1 + pureL2) % mod
const newPureL1 = pureP
const newPureL2 = pureL1
pureP = newPureP
pureL1 = newPureL1
pureL2 = newPureL2
}
return (P + L1 + L2 + A) % (10 ** 9 + 7)
}
Input
Output
#2 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0552_StudentAttendanceRecordII
{
private readonly int MOD_NUMBER = 1000000007;
public int CheckRecord(int n)
{
var dp = new long[n < 5 ? 6 : n + 1];
dp[0] = 1;
dp[1] = 2;
dp[2] = 4;
dp[3] = 7;
for (int i = 4; i < = n; i++)
dp[i] = ((2 * dp[i - 1]) % MOD_NUMBER + (MOD_NUMBER - dp[i - 4])) % MOD_NUMBER;
var sum = dp[n];
for (int i = 1; i < = n; i++)
sum += (dp[i - 1] * dp[n - i]) % MOD_NUMBER;
return (int)(sum % MOD_NUMBER);
}
}
}
Input
Output