Problem Description

The "Student Attendance Record II" problem asks us to determine how many possible attendance records of length n can be constructed, given certain rules. Each record is a string where each character represents a student's attendance on a day, and can be:

• 'A': Absent
• 'L': Late
• 'P': Present

• It must not contain more than one 'A' (absent) in total.
• It must not contain more than two continuous 'L' (late).

Thought Process

At first glance, it might seem reasonable to try generating all possible strings of length n and count those that meet the constraints. However, this brute-force approach would be extremely inefficient because the number of possible strings grows exponentially with n (specifically, 3^n).

To make the problem tractable, we need to use a more clever approach. The two main constraints ('A' at most once, 'L' not more than twice in a row) suggest that dynamic programming (DP) is a good fit. DP allows us to build up solutions for shorter records and use those to construct longer ones, while keeping track of the necessary state (such as how many 'A's we've used and how many consecutive 'L's are at the end).

The key insight is to keep track of:

• The number of 'A's used so far (0 or 1)
• The number of trailing 'L's (0, 1, or 2)

Solution Approach

We will use a dynamic programming (DP) approach. The main idea is to define a DP state that captures:

• i: the current length of the record
• a: the number of 'A's used so far (0 or 1)
• l: the number of consecutive 'L's at the end (0, 1, or 2)

1. Initialization: For length 0, there is one empty record: dp[0][0][0] = 1.
2. Transition: For each state dp[i][a][l], we can add one more character:
   • Add 'P': This resets the trailing 'L's to 0, and doesn't increase the 'A' count.
     dp[i+1][a][0] += dp[i][a][l]
   • Add 'A': Only if a == 0; this resets trailing 'L's to 0 and increases the 'A' count by 1.
     dp[i+1][1][0] += dp[i][0][l]
   • Add 'L': Only if l < 2; this increases the trailing 'L's by 1, 'A' count unchanged.
     dp[i+1][a][l+1] += dp[i][a][l]
   At each step, take modulo 10^9 + 7.
3. Result: The answer is the sum of all dp[n][a][l] for a in [0,1] and l in [0,1,2].

This method ensures that we never construct an invalid record, and efficiently builds up the solution for larger n using results from smaller ones.

Example Walkthrough

Let's walk through a small example with n = 2:

• All possible records of length 2:
  • "PP", "PL", "LP", "LL", "AP", "PA", "LA", "AL"
• Apply constraints:
  • No more than one 'A': All records above are valid except those with more than one 'A' (none here).
  • No more than two consecutive 'L's: All records above are valid since max consecutive 'L's is 2.
• Count valid records: All 8 records are valid for n=2.
• DP State transitions for n=2:
  • Start from dp[0][0][0] = 1
  • Build up dp[1][a][l] for all possible (a, l) using transitions as above.
  • Repeat for dp[2][a][l], then sum all dp[2][a][l] to get the result.

For larger n, the DP efficiently computes the answer without generating all records.

Time and Space Complexity

Brute-force approach:

• Time: O(3^n) (since each position can be 'A', 'L', or 'P')
• Space: O(n) for recursion stack or storing each record

Dynamic Programming approach:

• Time: O(n) (since there are n steps, and for each, we update at most 2 (A count) * 3 (L count) = 6 states)
• Space: O(n) (we can even optimize to O(1) by only keeping the previous step's DP states)

Summary

To solve the "Student Attendance Record II" problem, we use dynamic programming to efficiently count the number of valid attendance records. By keeping track of the number of 'A's used and the number of consecutive 'L's at the end, we avoid generating all possible strings and instead build up the answer iteratively. This approach is both elegant and efficient, leveraging the structure of the problem to achieve a solution that works for large input sizes.

Code Implementation

MOD = 10 ** 9 + 7

class Solution:
    def checkRecord(self, n: int) -> int:
        # dp[a][l]: number of ways with a 'A's and l trailing 'L's
        dp = [[0] * 3 for _ in range(2)]
        dp[0][0] = 1

        for _ in range(n):
            new_dp = [[0] * 3 for _ in range(2)]
            for a in range(2):
                for l in range(3):
                    # Add 'P'
                    new_dp[a][0] = (new_dp[a][0] + dp[a][l]) % MOD
                    # Add 'A'
                    if a == 0:
                        new_dp[1][0] = (new_dp[1][0] + dp[a][l]) % MOD
                    # Add 'L'
                    if l < 2:
                        new_dp[a][l+1] = (new_dp[a][l+1] + dp[a][l]) % MOD
            dp = new_dp

        return sum(dp[a][l] for a in range(2) for l in range(3)) % MOD
    

class Solution {
public:
    int checkRecord(int n) {
        const int MOD = 1e9 + 7;
        int dp[2][3] = {0};
        dp[0][0] = 1;

        for (int i = 0; i < n; ++i) {
            int new_dp[2][3] = {0};
            for (int a = 0; a < 2; ++a) {
                for (int l = 0; l < 3; ++l) {
                    // Add 'P'
                    new_dp[a][0] = (new_dp[a][0] + dp[a][l]) % MOD;
                    // Add 'A'
                    if (a == 0)
                        new_dp[1][0] = (new_dp[1][0] + dp[a][l]) % MOD;
                    // Add 'L'
                    if (l < 2)
                        new_dp[a][l+1] = (new_dp[a][l+1] + dp[a][l]) % MOD;
                }
            }
            memcpy(dp, new_dp, sizeof(dp));
        }

        int res = 0;
        for (int a = 0; a < 2; ++a)
            for (int l = 0; l < 3; ++l)
                res = (res + dp[a][l]) % MOD;
        return res;
    }
};
    

class Solution {
    public int checkRecord(int n) {
        int MOD = 1000000007;
        int[][] dp = new int[2][3];
        dp[0][0] = 1;

        for (int i = 0; i < n; i++) {
            int[][] newDp = new int[2][3];
            for (int a = 0; a < 2; a++) {
                for (int l = 0; l < 3; l++) {
                    // Add 'P'
                    newDp[a][0] = (newDp[a][0] + dp[a][l]) % MOD;
                    // Add 'A'
                    if (a == 0) {
                        newDp[1][0] = (newDp[1][0] + dp[a][l]) % MOD;
                    }
                    // Add 'L'
                    if (l < 2) {
                        newDp[a][l+1] = (newDp[a][l+1] + dp[a][l]) % MOD;
                    }
                }
            }
            dp = newDp;
        }
        int res = 0;
        for (int a = 0; a < 2; a++) {
            for (int l = 0; l < 3; l++) {
                res = (res + dp[a][l]) % MOD;
            }
        }
        return res;
    }
}
    

var checkRecord = function(n) {
    const MOD = 1e9 + 7;
    let dp = Array.from({length: 2}, () => Array(3).fill(0));
    dp[0][0] = 1;

    for (let i = 0; i < n; ++i) {
        let newDp = Array.from({length: 2}, () => Array(3).fill(0));
        for (let a = 0; a < 2; ++a) {
            for (let l = 0; l < 3; ++l) {
                // Add 'P'
                newDp[a][0] = (newDp[a][0] + dp[a][l]) % MOD;
                // Add 'A'
                if (a === 0)
                    newDp[1][0] = (newDp[1][0] + dp[a][l]) % MOD;
                // Add 'L'
                if (l < 2)
                    newDp[a][l+1] = (newDp[a][l+1] + dp[a][l]) % MOD;
            }
        }
        dp = newDp;
    }
    let res = 0;
    for (let a = 0; a < 2; ++a)
        for (let l = 0; l < 3; ++l)
            res = (res + dp[a][l]) % MOD;
    return res;
};