How do you solve Student Attendance Record II on LeetCode?

Student Attendance Record II (LeetCode #552) can be solved using Brute Force. The optimal approach is Brute Force with undefined time complexity and undefined space complexity. Key insight: The brute-force approach generates all possible attendance records of length n and checks each one for eligibility. This is simple but inefficient, as the number of combinations grows exponentially with n.

What is the time complexity of Student Attendance Record II?

The optimal solution for Student Attendance Record II runs in undefined time and uses undefined space. undefined

What algorithm or data structure is used to solve Student Attendance Record II?

Student Attendance Record II uses the following concepts: Dynamic Programming. The recommended patterns to study are: .

#552

Student Attendance Record II

Hard

Dynamic Programming

LeetCode ↗

Approaches

💡

Intuition

Time Space

The brute-force approach generates all possible attendance records of length n and checks each one for eligibility. This is simple but inefficient, as the number of combinations grows exponentially with n.

⚙️

Algorithm

3 steps

1Step 1: Generate all possible strings of length n using characters 'A', 'L', 'P'.
2Step 2: For each generated string, count the number of 'A's and check for 'L's in a row.
3Step 3: If the string has fewer than 2 'A's and no 'L's in a row for 3 or more days, count it as valid.

solution.py11 lines

1# Full working Python code
2from itertools import product
3
4MOD = 10**9 + 7
5def countAttendanceRecords(n):
6    valid_count = 0
7    for record in product('ALP', repeat=n):
8        record_str = ''.join(record)
9        if record_str.count('A') < 2 and 'LLL' not in record_str:
10            valid_count += 1
11    return valid_count % MOD

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.