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 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

Solution

Method 1 - Recursion

Code

Java
class Solution {
    public int checkRecord(int n) {
        return dfs(n, 0, 0, 0);
    }

	private static final int MOD = (int) 1e9 + 7;
    private int dfs(int n, int i, int a, int l) {
        if (i == n) {
            return 1;
        }
		
        // we set l to 0, as late has to be consecutive
        // as soon as we set A or P, we set L to 0
        int withP = dfs(n, i + 1, a, 0);
        int withA = a < 1 ? dfs(n, i + 1, a + 1, 0): 0; // absence can be max 1
        int withConsL = l < 2 ? dfs(n, i + 1, a, l + 1): 0; // consecutive late should be less than 3
        return ((withP + withA) % MOD + withConsL) % MOD;
    }
}

Complexity

  • ⏰ Time complexity: O(2^n) (not 3^n because only 1 A is allowed in the string).
  • 🧺 Space complexity: O(n) using recursion stack.

Method 2 - Top Down DP with memoization

Why DP?

We can use DP in this problem, the reason is:

Optimal Substructure

A problem has optimal substructure if the solution to the problem can be composed of optimal solutions to its subproblems. In the case of this student attendance record problem, we want to find the total number of valid attendance combinations for n days. Each day we make a decision: the student can be present (P), absent (A), or late (L), which will influence the remaining combinations. The solution to n days is built upon the solutions to n-1 days, which constitutes the optimal substructure property.

Overlapping Subproblem

A problem has overlapping subproblems when recursive problem-solving would visit the same subproblems multiple times. In previous code, dfs is called recursively with different combinations of days (i), absences (a), and late days (l). For the absent and late counts, there is a small range of valid inputs; specifically, a can only be 0 or 1, and l can only be 0, 1, or 2 before reaching a base case. If you consider various levels of the recursion and different paths through the recursive calls, you’d visualize a tree of recursive calls where many branches will call dfs with the same (n, i, a, l) parameters again and again.

 dfs(0,0,0)  Day 1
 +-- dfs(1,0,0)  Day 2 (P)
 |   +-- dfs(2,0,0)  Day 3 (PP) (Can add 'P', 'A', or 'L' on the next day)
 |   |   +-- ...
 |   +-- dfs(2,1,0)  Day 3 (PA) (Can add 'P' or 'L', 'A' is maxed out)
 |   |   +-- ... (Overlaps with dfs(2,0,0) when adding 'P')
 |   +-- dfs(2,0,1)  Day 3 (PL) (Can add 'P', 'A', one more 'L' is allowed)
 |       +-- ... (Overlaps with dfs(2,0,0) and dfs(2,1,0) when adding 'P' or 'A')
 +-- dfs(1,1,0)  Day 2 (A)
 |   +-- dfs(2,1,0)  Day 3 (AP)
 |   |   +-- ... (Already seen with dfs(2,1,0) under dfs(1,0,0))
 |   +-- dfs(2,1,1)  Day 3 (AL)
 |       +-- ... (Unique path since we have an 'A' before)
 +-- dfs(1,0,1)  Day 2 (L)
     +-- dfs(2,0,1)  Day 3 (LP)
     |   +-- ...
     +-- dfs(2,1,0)  Day 3 (LA)
     |   +-- ... (Overlaps with dfs(2,1,0) after dfs(1,0,0) with 'PA')
     +-- dfs(2,0,2)  Day 3 (LL)
         +-- ... (Can add only 'P' or 'A' next, no 'L' allowed due to rule)

Notice how certain calls to dfs occur multiple times with the same parameters, for example, dfs(2,1,0):

  • Once as a result of two ‘P’s followed by an ‘A’,
  • Once as a result of a ‘P’ followed by an ‘A’ and then another ‘P’.

Code

Java
class Solution {
    public int checkRecord(int n) {
        return dfs(n, 0, 0, 0, new int[n][2][3]);
    }

	private static final int MOD = (int) 1e9 + 7;
    private int dfs(int n, int i, int a, int l, int[][][] cache) {
        if (i == n) {
            return 1;
        }
        
		if(cache[i][a][l] != 0) {
			return cache[i][a][l];
		}
		
        // we set l to 0, as L has to be consecutive
        // as soon as we set A or P, we set L to 0
        int withP = dfs(n, i + 1, a, 0, cache);
        int withA = a < 1 ? dfs(n, i + 1, a + 1, 0, cache): 0; // absence can be max 1
        int withConsL = l < 2 ? dfs(n, i + 1, a, l + 1, cache): 0; // consecutive late should be less than 3
        int total = ((withP + withA) % MOD + withConsL) % MOD;
        return cache[i][a][l] = total;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Bottom-up DP

Algorithm

Let dp[i][a][l] denote the number of valid sequences of length i where:

  1. There can be at most a A’s in the entire sequence.
  2. There can be at most l trailing L’s.

We will fill dp till dp[n][1][2].

Base Case

On day 0, since there’s no prior record, all possibilities are valid (1 for each combination of a and l).

Recurrence relation
  • val = f[i - 1][a][2]: This represents the number of valid records ending on day i-1 with at most two consecutive ‘L’s (denoted by l = 2). This value is used as the starting point for building the current day’s possibilities. So, we just add P to the record, and hence we are just carrying forward this value for current dp[i][a][l].
  • val += f[i - 1][a - 1][2] if a > 0: This condition adds the number of valid records ending on day i-1 with one ‘A’ (denoted by a = 1) and at most two consecutive ‘L’s (k = 2). Since we can’t have more than one ‘A’, this is only added if a is greater than 0.
  • val += f[i - 1][j][l - 1]): This condition adds the number of valid records ending on day i-1 with the same number of ‘A’s (a) but one less consecutive ‘L’ (k - 1). This allows continuing a sequence of ‘L’s as long as it doesn’t exceed two.

Code

Java
class Solution {

	private static final int MOD = (int) 1e9 + 7;

	public int checkRecord(int n) {
		int[][][] dp = new int[n + 1][2][3];
		dp[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};

		for (int i = 1; i <= n; i++) {
			for (int a = 0; a < 2; a++) {
				for (int l = 0; l < 3; l++) {
					int val = dp[i - 1][a][2]; // ..P
					if (a > 0) {
						val = (val + dp[i - 1][a - 1][2]) % MOD; // ..A
					}
					if (l > 0) {
						val = (val + dp[i - 1][a][l - 1]) % MOD; // ..L	
					}				
					dp[i][a][l] = val;
				}
			}
		}

		return dp[n][1][2];
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) because 2*3*(n+1) = 6n ~ O(n)

Method 4 - State Optimized DP

We can actually solve this problem with O(1) space DP. Previous approach uses a 3D array dp, but we can just keep the number of valid records for a previous day, and calculate today’s value based on that.

We can use prevDP[a][l] to count valid student attendance records with a Absences and l consecutive late arrivals. Now a at max 2, and l is at max 3.

For a:

  • prevDP[0]: This represents the number of valid records ending on previous day with no ‘A’s (i.e., a = 0).
  • prevDP[1]: This represents the number of valid records ending on previous day with one ‘A’ (i.e., a = 1).

For l, we will similar values.

For day 0, we know all the values will be 1.

Code

Java
class Solution {

    private static final int MOD = (int) 1e9 + 7;

    public int checkRecord(int n) {
        int prevDP[][] = new int[2][3];
        prevDP[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};
        
        for(int i = 1; i <= n; i++){
            int newDP[][] = new int[2][3];
            for(int a = 0; a < 2; a++){
                for(int l = 0; l < 3; l++){
                    //Pick P
                    newDP[a][l] += prevDP[a][2];
                    if(a > 0){
                        //Pick A
                        newDP[a][l] += prevDP[a - 1][2];
                        newDP[a][l] %= MOD;
                    }
                    if(l > 0){
                        // Pick L
                        newDP[a][l] += prevDP[a][l - 1];
                        newDP[a][l] %= MOD;
                    }
                }
            }
            prevDP = newDP;
        }
        
        return prevDP[1][2];
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) (O(2*3) for matrix, hence O(1))

Method 5 - Matrix Exponentiation

From previous solution, we can see we get only 6 states, and next state is always generated from the current state.

#todo complete this step