Problem 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 modulo 10**9 + 7.

Constraints:

• 1 <= n <= 10**5

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

How to Solve

As this problem categorized in Hard, it is truly a hard problem. Easy solutions such as BSF or recursion get the Time Limit Exceeded error. So, it’s critical to improve the algorithm.

If we look into the problem well, we won’t take long to figure out this is a dynamic programming (DP) problem. A result of the given n depends on the result of n - 1 while n - 1 depends on n - 2. If we look into the problem further, we will realise the character pattern is not important. Looking at the number of patterns is the key to solve this problem. Again, if we look into the problem more, we will know it is a variation of famous Fibonacci sequence.

How to count is not straightforward like Fibonacci. The pattern counting is divided into two: with one A and without A. The initial values are based on n = 1.

• AnoL: one A and zero L — This is ‘A’. The initial value is 1.
• A1L: one A and one L — When n = 1, it’s not possible. The initial value = 0.
• A2L: one A and two Ls — When n = 1, it’s not possible. The initial value = 0.
• noAnoL: zero A and zero L — This is ‘P’. The initial value is 1.
• noA1L: zero A and one L — This is ‘L’. The initial value is 1.
• noA2L: zero A and two Ls — When n = 1, it’s not possible. The initial value = 0.

The next state, n = 2, can be calculated as:

• AnoL: sum of previous all 6 patterns
• A1L: previous AnoL
• A2L: previous A1L
• noAnoL: sum of previous three noA patterns
• noA1L: previous noAnoL
• noA2L: previous noA1L

In the end, sum of all 6 patterns is the answer.

Solution

• C++
• Java
• JavaScript
• Python
• Ruby

• class StudentAttendanceRecordTwo {
  public:
      int checkRecord(int n) {
          int mod = pow(10, 9) + 7;
          long long int AnoL = 1, A1L = 0, A2L = 0, noAnoL = 1, noA1L = 1, noA2L = 0, tmp;
          for (int i = 1; i < n; ++i) {
              tmp = (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod;
              A2L = A1L;
              A1L = AnoL;
              AnoL = tmp;
              tmp = (noAnoL + noA1L + noA2L) % mod;
              noA2L = noA1L;
              noA1L = noAnoL;
              noAnoL = tmp;
          }
          return (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod;
      }
  };
  

• class StudentAttendanceRecordTwo:
      def checkRecord(self, n: int) -> int:
          mod = 10 ** 9 + 7
          AnoL, A1L, A2L, noAnoL, noA1L, noA2L = 1, 0, 0, 1, 1, 0
          for _ in range(1, n):
              tmp = (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod
              A1L, A2L = AnoL, A1L
              AnoL = tmp
              tmp = (noAnoL + noA1L + noA2L) % mod
              noA1L, noA2L = noAnoL, noA1L
              noAnoL = tmp
          return (AnoL + A1L + A2L + noAnoL + noA1L + noA2L) % mod
  

• MOD = 10 ** 9 + 7
  
  # @param {Integer} n
  # @return {Integer}
  def check_record(n)
    a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l = 1, 0, 0, 1, 1, 0
    (1...n).each do |i|
      tmp = [a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
      a_1_l, a_2_l = a_no_l, a_1_l
      a_no_l = tmp
      tmp = [no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
      no_a_1_l, no_a_2_l = no_a_no_l, no_a_1_l
      no_a_no_l = tmp
    end
    [a_no_l, a_1_l, a_2_l, no_a_no_l, no_a_1_l, no_a_2_l].sum % MOD
  end
  

Complexities

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