# Student Attendance Record II
**Difficulty:** HARD
[External](https://leetcode.com/problems/student-attendance-record-ii)
Canonical: https://scaleengineer.com/dsa/problems/student-attendance-record-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## Problem
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`

# Approaches
## Top-Down Dynamic Programming (Memoization)
This approach uses recursion with memoization, a technique also known as top-down dynamic programming. We define a function that calculates the number of valid attendance records for a given number of remaining days `n`, the current count of absences, and the current count of consecutive lates. To avoid recomputing the same state multiple times, we store the result of each unique state `(n, absences, lates)` in a memoization table (a 3D array).
**Time:** O(n). The number of states is `n * 2 * 3`. Each state is computed only once, and each computation takes constant time. · **Space:** O(n). The space is dominated by the memoization table of size `n * 2 * 3`. The recursion stack depth also contributes O(n) space.
**Pros:** Relatively intuitive to formulate, as it directly translates the problem's recursive structure.; Correctly solves the problem within the time limits.
**Cons:** Can cause a `StackOverflowError` for very large `n` if the recursion depth limit is exceeded.; Slightly higher constant factor overhead compared to the iterative bottom-up approach due to function calls.
### Explanation
The core idea is to build the attendance record day by day, keeping track of the state necessary to check the validity rules. The state consists of the remaining length of the record to be generated, the total number of absences so far, and the number of consecutive lates at the very end of the partially built record.

When the function is called for a state, it first checks for base cases: if the state is already invalid (too many absences or lates), it returns 0. If the desired length is reached (`n=0`), it returns 1, signifying one valid record. If the result for the current state is already in our memoization table, we return it directly. Otherwise, we compute the result by recursively calling the function for the three possible next characters ('P', 'A', 'L'), updating the state accordingly, and summing up their results. The computed value is then stored in the memoization table to prevent redundant calculations in the future.

```java
class Solution {
    int MOD = 1_000_000_007;
    int[][][] memo;

    public int checkRecord(int n) {
        memo = new int[n + 1][2][3];
        for (int[][] arr2D : memo) {
            for (int[] arr1D : arr2D) {
                java.util.Arrays.fill(arr1D, -1);
            }
        }
        return solve(n, 0, 0);
    }

    private int solve(int n, int totalAbsences, int consecutiveLates) {
        if (totalAbsences >= 2 || consecutiveLates >= 3) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        if (memo[n][totalAbsences][consecutiveLates] != -1) {
            return memo[n][totalAbsences][consecutiveLates];
        }

        // Case 'P': Present
        long count = solve(n - 1, totalAbsences, 0);

        // Case 'A': Absent
        count = (count + solve(n - 1, totalAbsences + 1, 0)) % MOD;

        // Case 'L': Late
        count = (count + solve(n - 1, totalAbsences, consecutiveLates + 1)) % MOD;

        return memo[n][totalAbsences][consecutiveLates] = (int) count;
    }
}
```
### Algorithm
1.  Define a recursive function `solve(n, totalAbsences, consecutiveLates)` which returns the number of valid attendance records of length `n` given the current state.
2.  The state is defined by three parameters:
    *   `n`: the remaining number of days to consider.
    *   `totalAbsences`: the count of 'A's used so far.
    *   `consecutiveLates`: the count of consecutive 'L's at the end of the record built so far.
3.  **Base Cases:**
    *   If `totalAbsences >= 2` or `consecutiveLates >= 3`, the record is invalid. Return 0.
    *   If `n == 0`, we have successfully built a valid record of the required length. Return 1.
4.  **Memoization:**
    *   Use a 3D array `memo[n+1][2][3]` to store the results of subproblems. Initialize it with a sentinel value (e.g., -1).
    *   Before computing, check if `memo[n][totalAbsences][consecutiveLates]` already has a stored result. If so, return it.
5.  **Recursive Step:**
    *   Calculate the number of ways by considering the three possibilities for the current day:
        *   **Add 'P' (Present):** The number of absences remains the same, and consecutive lates reset to 0. Recursively call `solve(n - 1, totalAbsences, 0)`.
        *   **Add 'A' (Absent):** The number of absences increases by one, and consecutive lates reset to 0. Recursively call `solve(n - 1, totalAbsences + 1, 0)`.
        *   **Add 'L' (Late):** The number of absences remains the same, and consecutive lates increase by one. Recursively call `solve(n - 1, totalAbsences, consecutiveLates + 1)`.
    *   Sum the results from these three calls (modulo `10^9 + 7`).
6.  Store the computed result in the memoization table before returning.
7.  The initial call to the function will be `solve(n, 0, 0)`.

## Space-Optimized Bottom-Up Dynamic Programming
This approach uses bottom-up dynamic programming. Instead of starting from `n` and going down, we build the solution from the ground up. We compute the number of valid records for length 1, then use that to compute for length 2, and so on, up to `n`. The state is defined by `(length, total_absences, consecutive_lates)`. A key observation is that to compute the states for length `i`, we only need the results from length `i-1`. This allows for a significant space optimization, reducing the space complexity from O(n) to O(1).
**Time:** O(n). We iterate `n` times, and inside the loop, we perform a constant number of operations (iterating over the `2 * 3` states). · **Space:** O(1). We only need to store the DP states for the current and next day. The size of the DP table is `2 * 3`, which is constant.
**Pros:** Highly efficient in terms of space (O(1)).; Avoids recursion, thus preventing potential stack overflow issues.; Generally faster than the memoized recursion due to lower overhead.
**Cons:** The logic for transitions might be slightly less intuitive to formulate compared to the recursive approach for some developers.
### Explanation
We maintain a DP table that tracks the counts of valid sequences. A full DP table would be `dp[n+1][2][3]`, but we can optimize it to just `dp[2][3]` since we only need the previous day's counts to calculate the current day's counts.

We initialize the state for a 0-length string: `dp[0][0] = 1` (one way, the empty string). Then, we iterate from day 1 to `n`. In each iteration, we compute a new DP table `next_dp` based on the current `dp` table. For each state `(absences, lates)` in the current `dp` table, we see how adding 'P', 'A', or 'L' transitions it to a new state in `next_dp`. After calculating all transitions for the day, we replace the `dp` table with `next_dp` and proceed to the next day. Finally, we sum up all the counts in the final `dp` table to get the total number of valid records.

```java
class Solution {
    public int checkRecord(int n) {
        int MOD = 1_000_000_007;
        // dp[absences][consecutive_lates]
        long[][] dp = new long[2][3]; 
        dp[0][0] = 1; // Base case: one empty string

        for (int i = 0; i < n; i++) {
            long[][] nextDp = new long[2][3];
            for (int a = 0; a < 2; a++) {
                for (int l = 0; l < 3; l++) {
                    if (dp[a][l] == 0) continue;

                    // Add 'P'
                    nextDp[a][0] = (nextDp[a][0] + dp[a][l]) % MOD;

                    // Add 'A'
                    if (a + 1 < 2) {
                        nextDp[a + 1][0] = (nextDp[a + 1][0] + dp[a][l]) % MOD;
                    }

                    // Add 'L'
                    if (l + 1 < 3) {
                        nextDp[a][l + 1] = (nextDp[a][l + 1] + dp[a][l]) % MOD;
                    }
                }
            }
            dp = nextDp;
        }

        long total = 0;
        for (int a = 0; a < 2; a++) {
            for (int l = 0; l < 3; l++) {
                total = (total + dp[a][l]) % MOD;
            }
        }
        return (int) total;
    }
}
```
### Algorithm
1.  Define a DP table `dp[i][j][k]` to store the number of valid attendance records of length `i`, with a total of `j` absences, and ending with `k` consecutive lates.
2.  The dimensions of the state are:
    *   `i`: length of the record (from 0 to `n`).
    *   `j`: total absences (0 or 1).
    *   `k`: consecutive lates at the end (0, 1, or 2).
3.  **Initialization:** Set `dp[0][0][0] = 1`, representing a single empty string of length 0 with no absences or lates. All other initial DP values are 0.
4.  **Iteration:** Loop from `i = 1` to `n`. In each iteration, calculate the values for `dp[i]` based on the values from `dp[i-1]`.
5.  **Transitions:** For each state `(i-1, a, l)`, consider appending 'P', 'A', or 'L':
    *   **Append 'P':** A record of length `i-1` with `a` absences and `l` lates becomes a record of length `i` with `a` absences and 0 lates. Add `dp[i-1][a][l]` to `dp[i][a][0]`.
    *   **Append 'A':** If `a < 1`, this is a valid move. The new record has length `i`, `a+1` absences, and 0 lates. Add `dp[i-1][a][l]` to `dp[i][a+1][0]`.
    *   **Append 'L':** If `l < 2`, this is a valid move. The new record has length `i`, `a` absences, and `l+1` lates. Add `dp[i-1][a][l]` to `dp[i][a][l+1]`.
6.  **Space Optimization:** Notice that `dp[i]` only depends on `dp[i-1]`. We can optimize space to O(1) by using only two 2D arrays, one for the previous state (`dp_prev`) and one for the current state (`dp_curr`). After each iteration `i`, `dp_prev` is updated to `dp_curr`.
7.  **Final Result:** After the loop finishes, the total number of valid records of length `n` is the sum of all values in `dp[n]` (or the final `dp_curr` array in the optimized version).

## Matrix Exponentiation
This approach leverages the fact that the DP transitions form a system of linear recurrence relations. Such a system can be represented by a matrix transformation. We can define a state vector that holds the counts for all possible combinations of `(absences, lates)`, and a transition matrix that describes how these counts change from one day to the next. To find the counts for day `n`, we can raise this transition matrix to the power of `n` and apply it to the initial state vector. The matrix power can be calculated very efficiently using binary exponentiation, leading to a logarithmic time complexity.
**Time:** O(log n). The time is dominated by the matrix exponentiation algorithm, which performs O(log n) matrix multiplications. Each multiplication of two 6x6 matrices takes constant time (6^3 operations). · **Space:** O(1). The space required is for a few constant-size (6x6) matrices, regardless of the value of `n`.
**Pros:** Asymptotically the fastest approach, especially for very large `n`.; Constant space complexity.
**Cons:** Significantly more complex to conceptualize and implement compared to standard DP approaches.; The constant factor from matrix multiplication (`k^3`) can make it slower than the O(n) DP for smaller values of `n`.
### Explanation
The problem can be modeled as finding the number of paths of length `n` in a state graph. The nodes of the graph are the 6 possible states `(absences, lates)`, and the edges represent the transitions ('P', 'A', 'L'). The number of paths of length `n` from a starting node can be found by taking the `n`-th power of the graph's adjacency matrix.

Our transition matrix `T` acts as this adjacency matrix. We start with a single valid record of length 0 (the empty string), which corresponds to the state (A=0, L=0). Our initial state vector `S_0` is `[1, 0, 0, 0, 0, 0]^T`. The state vector after `n` days is `S_n = T^n * S_0`. We implement a `matrixPower` function that computes `T^n` in O(log n) time. The final answer is the sum of all elements in the resulting `S_n` vector.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int checkRecord(int n) {
        long[][] T = {
            {1, 1, 1, 0, 0, 0}, // P(A=0), L(A=0), LL(A=0) -> P(A=0)
            {1, 0, 0, 0, 0, 0}, // P(A=0) -> L(A=0)
            {0, 1, 0, 0, 0, 0}, // L(A=0) -> LL(A=0)
            {1, 1, 1, 1, 1, 1}, // Any state + A -> P(A=1); Any A=1 state + P -> P(A=1)
            {0, 0, 0, 1, 0, 0}, // P(A=1) -> L(A=1)
            {0, 0, 0, 0, 1, 0}  // L(A=1) -> LL(A=1)
        };

        if (n == 0) return 1;
        long[][] Tn = matrixPower(T, n);

        // S_n = Tn * S_0, where S_0 = [1, 0, 0, 0, 0, 0]^T
        // The result is the sum of all entries in the first column of Tn
        long result = 0;
        for(int i = 0; i < 6; i++) {
            result = (result + Tn[i][0]) % MOD;
        }
        
        return (int) result;
    }

    private long[][] matrixPower(long[][] base, int exp) {
        long[][] result = new long[6][6];
        for (int i = 0; i < 6; i++) result[i][i] = 1; // Identity matrix
        
        while (exp > 0) {
            if (exp % 2 == 1) result = multiply(result, base);
            base = multiply(base, base);
            exp /= 2;
        }
        return result;
    }

    private long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[6][6];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                for (int k = 0; k < 6; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }
}
```
### Algorithm
1.  **Represent State as a Vector:** The DP state `(total_absences, consecutive_lates)` can be flattened into a single state vector. There are `2 * 3 = 6` possible states. Let's map them:
    *   State 0: (A=0, L=0)
    *   State 1: (A=0, L=1)
    *   State 2: (A=0, L=2)
    *   State 3: (A=1, L=0)
    *   State 4: (A=1, L=1)
    *   State 5: (A=1, L=2)
    Let `S_i` be a column vector where `S_i[j]` is the count of records of length `i` ending in state `j`.
2.  **Formulate Transition Matrix:** The DP transitions are linear. We can find a 6x6 matrix `T` that transforms the state vector from day `i` to day `i+1`: `S_{i+1} = T * S_i`.
3.  **Derive the Matrix:** The entry `T[j][k]` is 1 if a record in state `k` can transition to state `j` by adding one character, and 0 otherwise. For example, adding 'P' to states 0, 1, or 2 (A=0) results in state 0 (A=0, L=0). So, `T[0][0]`, `T[0][1]`, and `T[0][2]` are 1. The full matrix is:
    ```
    [[1, 1, 1, 0, 0, 0],
     [1, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 0, 0],
     [1, 1, 1, 1, 1, 1],
     [0, 0, 0, 1, 0, 0],
     [0, 0, 0, 0, 1, 0]]
    ```
4.  **Use Matrix Exponentiation:** The state vector for day `n` is `S_n = T^n * S_0`. The initial state vector `S_0` (for a 0-length string) is `[1, 0, 0, 0, 0, 0]^T`.
5.  We can compute `T^n` efficiently using the binary exponentiation (or exponentiation by squaring) algorithm in O(k^3 log n) time, where `k=6` is the matrix dimension.
6.  **Calculate Final Result:** After computing `T^n`, the final state vector `S_n` is simply the first column of `T^n` (since `S_0` has a 1 only in the first position). The total number of valid records is the sum of all elements in `S_n`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = 1000000007;
public
  int checkRecord(int n) {
    long[][][] dp = new long[n][2][3];
```

### CPP

```cpp
constexpr int MOD = 1e9 + 7 ; class Solution { public: int checkRecord ( int n ) { using ll = long long ; vector < vector < vector < ll >>> dp ( n , vector < vector < ll >> ( 2 , vector < ll > ( 3 ))); // base case dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1 ; for ( int i = 1 ; i < n ; ++ i ) { // A dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ; // L dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ]; dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ]; dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ]; dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ]; // P dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ; dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ]) % MOD ; } ll ans = 0 ; for ( int j = 0 ; j < 2 ; ++ j ) { for ( int k = 0 ; k < 3 ; ++ k ) { ans = ( ans + dp [ n - 1 ][ j ][ k ]) % MOD ; } } return ans ; } };
```

### Python

```python
class Solution:
    # base case dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1 for i in range ( 1 , n ): # A dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod # L dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ] dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ] dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ] dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ] # P dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ] ) % mod ans = 0 for j in range ( 2 ): for k in range ( 3 ): ans = ( ans + dp [ n - 1 ][ j ][ k ]) % mod return ans
    def checkRecord(self, n: int) -> int: mod = int(1e9 + 7) dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n)]

```