552. Student Attendance Record II

Description

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

 

Solutions

Solution: Dynamic Programming

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

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const checkRecord = function (n) {
  const MODULO = 10 ** 9 + 7;
  const present = new Array(n + 1).fill(0);
  const late = new Array(n + 1).fill(0);
  const absent = new Array(n + 1).fill(0);

  present[1] = late[1] = absent[1] = 1;

  if (n > 1) {
    late[2] = present[1] + late[1] + absent[1]; // P, L, A
    absent[2] = present[1] + late[1]; // P, L
  }
  if (n > 2) absent[3] = (present[1] + late[1]) * 2; // PP, LL, PL, LP

  const sumTimes = (...nums) => nums.reduce((result, num) => (result + num) % MODULO);

  for (let index = 2; index <= n; index++) {
    const lastPresent = present[index - 1];
    const lastLate = late[index - 1];
    const lastAbsent = absent[index - 1];

    present[index] = sumTimes(lastPresent, lastLate, lastAbsent);
    if (index === 2) continue;

    late[index] = sumTimes(lastPresent, lastAbsent, present[index - 2], absent[index - 2]);
    if (index === 3) continue;

    absent[index] = sumTimes(lastAbsent, absent[index - 2], absent[index - 3]);
  }
  return sumTimes(present[n], late[n], absent[n]);
};