LeetCode 552: Student Attendance Record II

Problem Restatement

We are given an integer n.

We need to count how many attendance records of length n are eligible for an award.

Each record contains only three characters:

A record is valid only if:

1. It has strictly fewer than 2 absences.
2. It never has 3 or more consecutive late days.

Return the number of valid records modulo 10^9 + 7.

The official constraints are 1 <= n <= 10^5. The examples include n = 2, output 8; n = 1, output 3; and n = 10101, output 183236316.

Input and Output

Example function shape:

def checkRecord(n: int) -> int:
    ...

Examples

For:

n = 1

There are three possible records:

"P", "L", "A"

All are valid.

So the answer is:

3

For:

n = 2

There are nine total strings:

PP, PL, PA,
LP, LL, LA,
AP, AL, AA

Only "AA" is invalid because it has two absences.

So the answer is:

8

First Thought: Generate All Records

A direct solution is to generate every string of length n using "A", "L", and "P".

There are three choices for every position, so there are:

3 ** n

possible records.

For each record, we can check whether it has fewer than two "A" characters and does not contain "LLL".

This works for very small n, but it cannot handle n = 100000.

Problem With Brute Force

The number of records grows exponentially.

So we need to count valid records without building them.

The important observation is that we do not need the whole string. We only need enough state to know whether adding the next character keeps the record valid.

Key Insight

At any point, a partial record can be described by two pieces of state:

We never need to keep a state with a = 2, because that record is already invalid.

We never need to keep a state with l = 3, because that record is already invalid.

So there are only:

2 * 3 = 6

valid states.

For each day, we transition from old states to new states by adding one of three characters:

Dynamic Programming State

Let:

dp[a][l]

mean:

The number of valid records built so far with a absences and a current late streak of length l.

The possible values are:

a in {0, 1}
l in {0, 1, 2}

Before building any days, we have one empty record:

dp[0][0] = 1

All other states start at 0.

Algorithm

For each day from 1 to n:

1. Create a new DP table filled with zero.
2. For every state dp[a][l], try appending "P", "A", and "L".
3. Append "P":

   ndp[a][0] += dp[a][l]
4. Append "A" only if a == 0:

   ndp[1][0] += dp[0][l]
5. Append "L" only if l < 2:

   ndp[a][l + 1] += dp[a][l]
6. Replace dp with ndp.

At the end, sum all six states.

Correctness

The DP state records exactly the information needed to determine whether the next character can be added.

For absences, the only relevant fact is whether the record already has zero or one "A". If it already has one, adding another "A" would make the record invalid.

For late days, the only relevant fact is the current suffix length of consecutive "L" characters. If the suffix length is two, adding another "L" would create "LLL" and make the record invalid.

Each transition appends exactly one valid next character. "P" always keeps the record valid and resets the late streak. "A" is allowed only when no absence has appeared before. "L" is allowed only when the current late streak is less than two.

Every valid attendance record of length n can be produced by these transitions one character at a time. Every record produced by these transitions satisfies both rules. Therefore, summing all DP states after n days gives exactly the number of valid records.

Complexity

Implementation

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7

        dp = [[0] * 3 for _ in range(2)]
        dp[0][0] = 1

        for _ in range(n):
            ndp = [[0] * 3 for _ in range(2)]

            for a in range(2):
                for l in range(3):
                    count = dp[a][l]
                    if count == 0:
                        continue

                    # Add 'P': reset late streak.
                    ndp[a][0] = (ndp[a][0] + count) % MOD

                    # Add 'A': allowed only if no absence was used.
                    if a == 0:
                        ndp[1][0] = (ndp[1][0] + count) % MOD

                    # Add 'L': allowed only if it does not create 'LLL'.
                    if l < 2:
                        ndp[a][l + 1] = (ndp[a][l + 1] + count) % MOD

            dp = ndp

        return sum(sum(row) for row in dp) % MOD

Code Explanation

We start with:

dp[0][0] = 1

This represents the empty record. It has zero absences and zero consecutive late days.

For every day, we build a fresh table:

ndp = [[0] * 3 for _ in range(2)]

This table stores counts after adding one more character.

Adding "P" is always valid:

ndp[a][0] = (ndp[a][0] + count) % MOD

It does not change the absence count, and it resets the late streak.

Adding "A" is allowed only from states with a == 0:

if a == 0:
    ndp[1][0] = (ndp[1][0] + count) % MOD

After adding "A", the absence count becomes 1, and the late streak resets.

Adding "L" is allowed only when l < 2:

if l < 2:
    ndp[a][l + 1] = (ndp[a][l + 1] + count) % MOD

This extends the current late streak by one.

After processing all days, every valid record of length n belongs to exactly one of the six DP states. So we return their sum.

Testing

def run_tests():
    s = Solution()

    assert s.checkRecord(1) == 3
    assert s.checkRecord(2) == 8
    assert s.checkRecord(3) == 19
    assert s.checkRecord(4) == 43
    assert s.checkRecord(10101) == 183236316

    print("all tests passed")

run_tests()