Student Attendance Record II

Problem Statement

In this problem, we are given a scenario where a student's attendance is recorded in a string format, with each character representing one of three statuses: Absent ('A'), Late ('L'), and Present ('P'). For a student to be considered for an attendance award, two criteria must be satisfied: the student must have less than two days of absence and must not be late for three consecutive days. Given an integer n, which indicates the length of the attendance record, our task is to compute how many possible attendance records of that length would make the student eligible for the award. Due to potentially large outputs, results should be returned modulo 10^9 + 7.

Examples

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

Approach and Intuition

Understanding this problem requires analyzing how combinations of 'A', 'L', and 'P' can be arranged to satisfy the given criteria for eligibility:

1. Generate all possible sequences of attendance records of length n.
2. Ensure that these records have fewer than two 'A's.
3. Ensure that no sequence contains three or more consecutive 'L's.

The nuances in such sequence generation involve significant combinatorial calculations, especially as n becomes large. Here's the approach:

Dynamic Programming Solution

• Base Cases: Start with initializing the counts of sequences of shorter lengths which are simpler to calculate manually or have obvious results.
• Transitional Formula: Establish a relationship where the count for each length n can be derived using the counts from shorter lengths. This typically involves adding a character to shorter valid sequences while maintaining the award criteria.

Modulo Operation

• Since results can be substantial due to the combinatorial explosion as n increases, and to avoid overflow as well as adhere to problem constraints, we use modulo 10^9 + 7 at every step of our computation.

Edge Cases

1. Smaller values of n: These are straightforward and serve as base cases for building up to larger n.
2. Detection of sequences ineligible for an award due to AAA, AAAA (or more continous 'A's) and extensive sequences of 'L': Incorporating mechanisms to skip such combinations saves computation.

By implementing dynamic programming efficiently, these observations can be executed with significant optimizations, leading to feasible solutions even for large values of n, up to the upper constraint of 105.

Solutions

class Solution {
public:
    int countValidSequences(int length) {
        int MODULO = 1000000007;
        vector<vector<int>> currentState = vector<vector<int>>(2, vector<int>(3, 0));
        vector<vector<int>> nextState = vector<vector<int>>(2, vector<int>(3, 0));
            
        currentState[0][0] = 1;
    
        for (int len = 0; len < length; ++len) {
            for (int absences = 0; absences <= 1; ++absences) {
                for (int lates = 0; lates <= 2; ++lates) {
                    nextState[absences][0] = (nextState[absences][0] + currentState[absences][lates]) % MODULO;
                    if (absences < 1) {
                        nextState[absences + 1][0] = (nextState[absences + 1][0] + currentState[absences][lates]) % MODULO;
                    }
                    if (lates < 2) {
                        nextState[absences][lates + 1] = (nextState[absences][lates + 1] + currentState[absences][lates]) % MODULO;
                    }
                }
            }
    
            currentState = nextState;
            nextState = vector<vector<int>>(2, vector<int>(3, 0));
        }
    
        int result = 0;
        for (int absences = 0; absences <= 1; ++absences) {
            for (int lates = 0; lates <= 2; ++lates) {
                result = (result + currentState[absences][lates]) % MODULO;
            }
        }
        return result;
    }
};