Leetcode 552: Student Attendance Record II

Problem Description

#

Check out the problem on Leetcode

You have a string representing the attendance record of a student:

• A = Absent
• L = Late
• P = Present

You must find the number of strings of length n that have the following properties:

• only contain the letters (A,L,P)
• contain less than two A’s
• don’t contain any occurences of ‘LLL’

Solution 1 - Using Recurrences

#

This approach will be to use recurrence relations to calculate the number of combinations whilst avoiding considering the actual possible strings.

Creating a recurrence (ignoring absences)

#

Let \(S_n\) be a valid string with no absences. Let \(F(n)\) be the number of such strings. We can make a valid string \(S_n\) using shorter ones:

• \(S_{n-1}\) + P
• \(S_{n-2}\) + PL
• \(S_{n-3}\) + PLL

We can get all possible strings (longer than 3) this way with no double counting. For example, PLLPPL = PLL + P + PL.

Therefore: \(F(n)=F(n-1)+F(n-2)+F(n-3)\)

Accounting for absences

#

We are allowed to have a maximum of one absence.

If the absence is after lesson \(i\), then we have a no-absence string of length \(i\) before it and a no-absence string of length \(n-i-1\) after it. For example, if we have 10 lessons and the student is absent for lesson 3:

$$ \text{string} = S_2 + A + S_7 $$

Therefore, the number of valid strings for a given absence = \(F(i) * F(n-i-1)\)

We can find the total number of valid strings by iterating over all possible lessons up to \(i=n/2\) and then multiply by two because \(F(2)*F(7) = F(7)*F(2)\).

Finally, we add \(F(n)\) to the total, for the situation where the student has no absences.

Complexity

#

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

Code

#

int checkRecord(const int& n) {
    // check for base case
    if(n==1){
        return 3;
    }
    else if(n==2){
        return 8;
    }

    // F[n] = number of ways to form a string of length n with no absences
    vector<long long> F(n+1, 0ll);
    F[0]=1;
    F[1]=2;
    F[2]=4;

    const long long MOD = 1000000007;
    for(int i=3; i<=n; i++){
        F[i] = (F[i-3]+F[i-2]+F[i-1]) % MOD;
    }
    long long numWithAbsences = 0;
    for(int i=0; i<n/2; i++){
        numWithAbsences += (F[i]*F[n-i-1]) % MOD;
    }
    numWithAbsences *= 2;
    if(n % 2 == 1){
        numWithAbsences += F[n/2]*F[n/2];
    }

    return (F[n] + numWithAbsences) % MOD;
}

Solution 2 - Matrix Exponentiation

#

Often in questions where you have a limited number of states you can be in, and you’re trying to find the total number of ways to generate some sequence of these, you can represent this using a transition matrix.

The ‘state’ of our string in this case depends on the last letters and whether the student has been absent before. In our transition matrix, we will put a \(1\) in position \((x,y)\) if we can move from state \(x\) to state \(y\). We will represent a state where we have already been absent using \(x^A\).

To understand this matrix, lets look at row \(L^A\). This means the last letter is \(L\) and the student has been absent before. Therefore, the next day can either be another late day, in which case we move to state \({LL}^A\), or the student is present, in which case we move to \(P^A\). No other states are possible, so the rest of the row values are 0.

using the matrix

#

This matrix represents all the possible letters you can add in one day, depending on your state. If we want to find the number of strings we can add in \(n\) days, then we can just multiply \(n\) of these matrices together (add one letter, then another, then another…)

We can find the exponent of the matrix in \(O(\log n)\)using exponentiation by squaring. Essentially, we keep squaring the matrix \(M\) so we get \([M, M^2, M^4, M^8, M^{16} \dots ]\). Since this question uses modular arithmetic, we will find these values mod m.

We multiply values in the list together to get our exact exponent. For example, if we wanted to find \(M^{13}\), we would use \(M^8 \cdot M^4 \cdot M\).

Once we have our final transition matrix, we want to sum together all the different paths that start with the possible starting states. The mathematical way to write this is to first get the dot product of our starting states [1,1,1,0,0,0,0] (since we must start with an A,P or L) with our final transition matrix, which will tell us how many ways there are to get to each final state.

For example, if we calculate the dot product of our starting states with \(M^5\), we get [13,13,7,4,30,19,8], which means that there are 19 ways of reaching the state \(L^A\).

Therefore, to get the total number of paths to any final state, we take the sum of these numbers.

Code

#

I used numpy to calculate the matrix operations efficiently.

def solve_with_matrix(n):
    base = np.array([
        [0, 0, 0, 0, 1, 1, 0],
        [1, 1, 1, 0, 0, 0, 0],
        [1, 1, 0, 1, 0, 0, 0],
        [1, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 1],
        [0, 0, 0, 0, 1, 0, 0]
    ], dtype=np.int64)

    final_transition_matrix = np.eye(7, dtype=np.int64)
    MOD = 10**9+7
    n = n-1
    while(n>0):
        if(n%2==1):
            final_transition_matrix = np.dot(final_transition_matrix, base)%MOD
        
        base = np.dot(base, base) % MOD
        n //= 2

    start = np.array([1,1,1,0,0,0,0], dtype=np.int64)
    return np.dot(start, final_transition_matrix).sum() % MOD

Complexity

#

• Time Complexity: \(O(\log n)\)
• Space Complexity: \(O(1)\)