HardNo. 0552

Student Attendance Record II — LeetCode 552 Python Solution

Topics
Dynamic Programming
Reading time
3 min

The problem

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters: 'A': Absent.

Example

Input
n = 2
Output
8
Explanation
There are 8 records with length 2 that are eligible for an award:

Python solution

PythonSolution
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

Complexity

Time
O(n·m) (typical)
Space · auxiliary
O(n·m)or optimized

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 552. Student Attendance Record II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0553Optimal DivisionMedium
0546Remove BoxesHard
054201 MatrixMedium
0010Regular Expression MatchingHard
0022Generate ParenthesesMedium
0032Longest Valid ParenthesesHard

Frequently asked questions

How hard is LeetCode 552. Student Attendance Record II?

LeetCode 552. Student Attendance Record II is rated Hard on LeetCode.

What topics does LeetCode 552. Student Attendance Record II cover?

LeetCode 552. Student Attendance Record II is tagged Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.