# Student Attendance Record II Problem

## Description

LeetCode Problem 552.

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^9 + 7.

Example 1:

``````1
2
3
4
5
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:

``````1
2
Input: n = 1
Output: 3
``````

Example 3:

``````1
2
Input: n = 10101
Output: 183236316
``````

Constraints:

• 1 <= n <= 10^5

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
long long int mod = 1e9 + 7;
long long int dp[100001][2][3];

int helper(int n, int absent, int late) {
if (late >= 3 || absent >= 2)
// not an eligible record condition
return 0;
if (n == 0)
// recurrence call till n == 0, i.e. we got an eligible record
return 1;

//Memoization
if (dp[n][absent][late] != -1)
return dp[n][absent][late];

//Recurrence calls
int p_selected = helper(n-1, absent, 0); // if we selected Present
int a_selected = helper(n-1, absent + 1, 0); // if we selected Absent
int l_selected = helper(n-1, absent, late + 1); // if we selected Late

// Output = Sum of all three recurrence call outputs
return dp[n][absent][late] = (p_selected%mod + a_selected%mod + l_selected%mod ) % mod;
}

int checkRecord(int n) {
//Initializing dp with -1
memset(dp, -1, sizeof(dp));
return helper(n, 0, 0);
}
};
``````