Problem statement

https://leetcode.com/problems/student-attendance-record-ii/

Solution 1

We need to carefully consider the states we have: let $a_n$ be a record without $A$, ending with [not L, L, L], $b_n$ be a record without $A$, ending with [not L, L], $c_n$ be a record without $A$, ending with [not L], $d_n$ be a record with $A$, ending with [not L, L, L], $e_n$ be a record with $A$, ending with [not L, L], $f_n$ be a record with $A$, ending with [not L]. Then we can write down the following recurrent: $A_{n+1} = B_n, B_{n+1} = C_n, C_{n+1} = A_n+B_n+C_n, D_{n+1} = E_n, E_{n+1} = F_n, F_{n+1} = A_n + B_n + C_n + D_n + E_n + F_n$.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def checkRecord(self, n):
        a,b,c,d,e,f = 0,1,1,0,0,1
        N = 10**9 + 7
        for i in range(n-1):
            a,b,c,d,e,f = b,c,a+b+c,e,f,a+b+c+d+e+f
            a,b,c,d,e,f = a%N,b%N,c%N,d%N,e%N,f%N
        
        return (a+b+c+d+e+f)%N

Solution 2

There is alternative solution, using matrix exponentiation. Notice that it will work, because dimension of matrix is <= 8, see remark on the page patterns.

Complexity

Time complexity is O(m^3*log n), where m = 6, space complexity is O(m^2).

Code

import numpy as np

class Solution(object):
    def checkRecord(self, n):
        A = np.matrix([[0, 1, 0, 0, 0, 0],
                       [0, 0, 1, 0, 0, 0],
                       [1, 1, 1, 0, 0, 0],
                       [0, 0, 0, 0, 1, 0],
                       [0, 0, 0, 0, 0, 1],
                       [1, 1, 1, 1, 1, 1]])
        
        power = A
        N = 10**9 + 7
        while n:
            if n & 1:
                power = (power * A) % N
            A = A**2 % N
            n //= 2
            
        return int(power[5, 2])