#552

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Student Attendance Record II

The Student Attendance Record II problem explores counting valid student attendance sequences using dynamic programming with state transitions.

dynamic programming

Problem Statement

You are given a record of student attendance where each character represents a day’s status: 'P' for present, 'A' for absent, and 'L' for late. A student is eligible for an attendance award if they have no more than one 'A' and no more than one 'L' in the record.

Given an integer n, determine how many valid attendance records of length n satisfy the above criteria. The result should be computed modulo 10^9 + 7 due to large potential numbers.

Examples

Example 1

Input: n = 2

Output: 8

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 details omitted.

Example 3

Input: n = 10101

Output: 183236316

Example details omitted.

Constraints

1 <= n <= 105

Solution Approach

State Transition Dynamic Programming

Use dynamic programming (DP) to track the number of valid records. Define a state transition that captures the possibilities for 'P', 'A', and 'L'. Maintain a DP array with three states: no 'A' or 'L', one 'L' with no 'A', and one 'A' with no 'L'. Transition the states based on previous results.

Modulo Arithmetic

Since the number of valid sequences can be large, all computations are done modulo 10^9 + 7. This helps avoid overflow issues and ensures that we return the correct answer even for the largest inputs.

Iterative DP Solution

Iterate from 1 to n, updating the DP table for each step. Each step should consider the potential transitions for the next character ('P', 'A', 'L') based on the current state. The solution’s time complexity is O(n), and space complexity is O(1) due to constant space optimization.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of this solution is O(n) since the state transitions are computed iteratively for each value from 1 to n. The space complexity is O(1) because we only need a fixed number of variables to keep track of the states, regardless of the value of n.

What Interviewers Usually Probe

Check if the candidate understands how state transitions work in dynamic programming.
Ensure they are aware of the modulo operation to handle large numbers.
Evaluate their approach to optimizing space complexity in this problem.

Common Pitfalls or Variants

Common pitfalls

Not handling the modulo operation properly could lead to incorrect results.
Misunderstanding the state transitions can result in missing valid sequences.
Using excessive space for the DP array instead of optimizing it to O(1).

Follow-up variants

Consider variants where the student can have more than one late arrival, increasing the complexity of the state transitions.
Modify the problem by changing the number of absences allowed (e.g., 3 absences instead of 1).
Extend the problem to account for different types of attendance records (e.g., early arrivals, half-day attendance).

FAQ

What is the primary pattern used in the Student Attendance Record II problem?

The primary pattern is state transition dynamic programming, where you track the number of valid attendance sequences based on previous states.

Why is modulo 10^9 + 7 necessary in this problem?

The modulo operation ensures that the number of valid sequences remains within manageable bounds, avoiding overflow in large calculations.

How can I optimize space complexity in dynamic programming for this problem?

You can optimize space by maintaining only the current and previous states, reducing the space complexity to O(1).

What is the time complexity of solving the Student Attendance Record II problem?

The time complexity is O(n) because the dynamic programming table is updated iteratively for each value from 1 to n.

How does state transition dynamic programming work in this problem?

State transition dynamic programming tracks the number of valid records based on previous attendance records, ensuring no more than one 'A' and one 'L' in each sequence.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def checkRecord(self, n: int) -> int:
        @cache
        def dfs(i, j, k):
            if i >= n:
                return 1
            ans = 0
            if j == 0:
                ans += dfs(i + 1, j + 1, 0)
            if k < 2:
                ans += dfs(i + 1, j, k + 1)
            ans += dfs(i + 1, j, 0)
            return ans % mod

        mod = 10**9 + 7
        ans = dfs(0, 0, 0)
        dfs.cache_clear()
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def checkRecord(self, n: int) -> int:
        @cache
        def dfs(i, j, k):
            if i >= n:
                return 1
            ans = 0
            if j == 0:
                ans += dfs(i + 1, j + 1, 0)
            if k < 2:
                ans += dfs(i + 1, j, k + 1)
            ans += dfs(i + 1, j, 0)
            return ans % mod

        mod = 10**9 + 7
        ans = dfs(0, 0, 0)
        dfs.cache_clear()
        return ans

Continue Practicing

#553 optimal division #546 remove boxes #542 01 matrix