LeetCode 552 - Student Attendance Record II

The problem asks us to count how many attendance records of length n satisfy two award eligibility rules. Each attendance record is a string made up of three possible characters: - 'P' means the student was present. - 'A' means the student was absent.

leetcodeharddynamic-programming

LeetCode Problem 552

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many attendance records of length n satisfy two award eligibility rules.

Each attendance record is a string made up of three possible characters:

  • 'P' means the student was present.
  • 'A' means the student was absent.
  • 'L' means the student was late.

A record is considered valid only if:

  1. The total number of 'A' characters is strictly less than 2, meaning there can be at most one absence in the entire string.
  2. The record never contains three consecutive 'L' characters.

We are given an integer n, representing the number of days, and we must return the number of valid attendance records of length n.

Since the answer can become extremely large, we return the result modulo 10^9 + 7.

The constraint 1 <= n <= 10^5 is very important. A brute-force approach would consider all possible strings of length n. Since each position has three choices, there are 3^n total possibilities. Even for moderate values of n, this becomes impossibly large. Therefore, we need a dynamic programming solution that builds answers incrementally while avoiding recomputation.

The important edge cases include very small values such as n = 1, where every single-character string is valid, and larger values where repeated late sequences or multiple absences must be carefully excluded. Another tricky scenario is correctly handling transitions that would create "LLL" or a second 'A'.

Approaches

Brute Force

A straightforward approach is to generate every possible attendance string of length n and check whether it satisfies the rules.

For every position, we can choose:

  • 'P'
  • 'A'
  • 'L'

This produces 3^n total strings. For each generated string, we count the number of absences and check whether "LLL" appears anywhere.

This method is correct because it explicitly examines every possible attendance record and filters out invalid ones. However, it is far too slow for the constraints. When n = 100000, even storing all possibilities is impossible.

Key Insight

The important observation is that the validity of a partial attendance record depends only on a small amount of information:

  • How many absences have been used so far, either 0 or 1
  • How many consecutive late days currently exist, either 0, 1, or 2

We do not need the full string history.

This naturally leads to dynamic programming.

We define a DP state based on:

  • Current length processed
  • Number of absences used
  • Current consecutive late streak

At every step, we try appending:

  • 'P', which resets the late streak
  • 'A', only if no absence has been used yet
  • 'L', only if the current late streak is less than 2

Because there are only 2 * 3 = 6 meaningful states per position, the solution becomes extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n * n) O(n) Generates every possible string and validates it
Optimal Dynamic Programming O(n) O(1) Tracks only absence count and late streak

Algorithm Walkthrough

Dynamic Programming State

We define:

dp[a][l]

Where:

  • a is the number of absences used so far, either 0 or 1
  • l is the current consecutive late streak, 0, 1, or 2

The value stored is the number of valid sequences currently in that state.

Step-by-Step Process

  1. Initialize the DP table.

At the beginning, before processing any characters, we have exactly one empty sequence:

  • 0 absences
  • 0 consecutive late days

So:

dp[0][0] = 1
  1. Process each day one by one.

For every existing state, we attempt to append one additional character. 3. Append 'P'.

Appending 'P' is always valid.

It does not increase the absence count, and it resets the late streak to 0.

Transition:

next_dp[a][0] += dp[a][l]
  1. Append 'A'.

We can only append 'A' if we have not already used an absence.

This increases the absence count to 1 and resets the late streak.

Transition:

next_dp[1][0] += dp[0][l]
  1. Append 'L'.

We can only append 'L' if the current late streak is less than 2.

This increases the late streak by one.

Transition:

next_dp[a][l + 1] += dp[a][l]
  1. Replace the old DP table with the newly computed one.

After processing all states for the current day, the new table becomes the current state. 7. Repeat until all n positions are processed. 8. Sum all valid states.

Every remaining state represents a valid attendance sequence, so we add them all together.

Why it works

The DP state captures exactly the information needed to determine whether future additions remain valid. The award rules depend only on:

  • Total absences so far
  • Current consecutive late streak

No other historical information matters. Since every valid sequence transitions correctly into future valid states, and every invalid transition is excluded, the DP enumerates all valid attendance records exactly once.

Python Solution

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

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

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

            for absences in range(2):
                for late_streak in range(3):
                    current = dp[absences][late_streak]

                    if current == 0:
                        continue

                    # Add 'P'
                    next_dp[absences][0] = (
                        next_dp[absences][0] + current
                    ) % MOD

                    # Add 'A'
                    if absences == 0:
                        next_dp[1][0] = (
                            next_dp[1][0] + current
                        ) % MOD

                    # Add 'L'
                    if late_streak < 2:
                        next_dp[absences][late_streak + 1] = (
                            next_dp[absences][late_streak + 1] + current
                        ) % MOD

            dp = next_dp

        result = 0

        for absences in range(2):
            for late_streak in range(3):
                result = (result + dp[absences][late_streak]) % MOD

        return result

The implementation begins by creating a 2 x 3 DP table. The first dimension represents how many absences have been used, and the second dimension tracks the current consecutive late streak.

The initial state corresponds to the empty sequence.

For each day, we create a fresh DP table called next_dp. This prevents updates from interfering with states that still need processing in the current iteration.

For every valid state, we attempt three transitions:

  • Append 'P'
  • Append 'A'
  • Append 'L'

Each transition updates the appropriate future state while applying modulo arithmetic to avoid integer overflow.

At the end of every iteration, dp becomes next_dp.

Finally, we sum all states because every remaining state corresponds to a valid attendance record.

Go Solution

func checkRecord(n int) int {
	const MOD int = 1000000007

	dp := [2][3]int{}
	dp[0][0] = 1

	for i := 0; i < n; i++ {
		nextDP := [2][3]int{}

		for absences := 0; absences < 2; absences++ {
			for lateStreak := 0; lateStreak < 3; lateStreak++ {
				current := dp[absences][lateStreak]

				if current == 0 {
					continue
				}

				// Add 'P'
				nextDP[absences][0] =
					(nextDP[absences][0] + current) % MOD

				// Add 'A'
				if absences == 0 {
					nextDP[1][0] =
						(nextDP[1][0] + current) % MOD
				}

				// Add 'L'
				if lateStreak < 2 {
					nextDP[absences][lateStreak+1] =
						(nextDP[absences][lateStreak+1] + current) % MOD
				}
			}
		}

		dp = nextDP
	}

	result := 0

	for absences := 0; absences < 2; absences++ {
		for lateStreak := 0; lateStreak < 3; lateStreak++ {
			result = (result + dp[absences][lateStreak]) % MOD
		}
	}

	return result
}

The Go implementation mirrors the Python logic closely. Instead of nested lists, it uses fixed-size arrays because the DP dimensions are known at compile time.

Modulo arithmetic is performed after every update to prevent overflow. Go integers are sufficient because intermediate values are always reduced modulo 10^9 + 7.

Unlike Python, Go does not support dynamic resizing as conveniently, so fixed arrays make the implementation cleaner and more efficient.

Worked Examples

Example 1

Input:

n = 2

Initial state:

Absences Late Streak Count
0 0 1

After Day 1

From (0,0):

  • Add 'P' → (0,0)
  • Add 'A' → (1,0)
  • Add 'L' → (0,1)

Resulting DP:

Absences Late Streak Count
0 0 1
0 1 1
1 0 1

Total valid sequences after one day:

P, A, L

After Day 2

Process every state again.

From (0,0):

  • 'P' → (0,0)
  • 'A' → (1,0)
  • 'L' → (0,1)

From (0,1):

  • 'P' → (0,0)
  • 'A' → (1,0)
  • 'L' → (0,2)

From (1,0):

  • 'P' → (1,0)
  • 'L' → (1,1)

Final DP:

Absences Late Streak Count
0 0 2
0 1 1
0 2 1
1 0 3
1 1 1

Total:

2 + 1 + 1 + 3 + 1 = 8

Answer:

8

Example 2

Input:

n = 1

Possible valid strings:

P, A, L

Total:

3

Example 3

Input:

n = 10101

The DP runs efficiently because only six states are maintained at every step.

Final answer:

183236316

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each day processes only 6 DP states
Space O(1) The DP table size never grows

The algorithm performs a constant amount of work for every position in the attendance record. Since there are only six possible states, each iteration is effectively constant time.

The space complexity is constant because we only store the current DP table and the next DP table, each of fixed size 2 x 3.

Test Cases

solution = Solution()

assert solution.checkRecord(1) == 3
# Single character strings: P, A, L

assert solution.checkRecord(2) == 8
# Provided example

assert solution.checkRecord(3) == 19
# Small manual verification case

assert solution.checkRecord(4) == 43
# Checks multiple DP transitions

assert solution.checkRecord(5) == 94
# Larger small case

assert solution.checkRecord(10) == 3536
# Medium-sized input

assert solution.checkRecord(10101) == 183236316
# Large provided example

assert solution.checkRecord(100000) >= 0
# Stress test for maximum constraint

assert solution.checkRecord(2) != 9
# Ensures invalid "AA" is excluded

assert solution.checkRecord(3) != 27
# Ensures invalid sequences are filtered
Test Why
n = 1 Smallest valid input
n = 2 Verifies sample output
n = 3 Checks multiple branching transitions
n = 4 Ensures DP accumulates correctly
n = 5 Additional correctness validation
n = 10 Medium-size consistency check
n = 10101 Provided large example
n = 100000 Maximum constraint stress test
Invalid count checks Ensures forbidden states are excluded

Edge Cases

One important edge case is n = 1. With only one day, every single-character string is valid because no string can contain two absences or three consecutive late days. A buggy implementation might accidentally mishandle initialization or transitions and return an incorrect count. The DP initialization with dp[0][0] = 1 correctly handles this case.

Another important edge case involves sequences that would create three consecutive late days. For example, when the current late streak is already 2, adding another 'L' must be forbidden. The implementation explicitly checks late_streak < 2 before allowing the transition, preventing invalid sequences such as "LLL".

A third tricky edge case is handling the second absence. Once a sequence already contains one 'A', adding another absence would violate the rules. The implementation only allows the 'A' transition when absences == 0, ensuring that no state ever contains more than one absence.

A final consideration is very large values of n, especially n = 100000. Recursive solutions without memoization would overflow the call stack or time out. The iterative DP approach avoids recursion entirely and uses only constant memory, making it safe and efficient for the largest inputs.