Introduction

In this blog post, we will explore how to solve the LeetCode problem "552" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 'L': Late. 'P': Present. Any student is eligible for an attendance award if they meet both of the following criteria: The student was absent ('A') for strictly fewer than 2 days total. The student was never late ('L') for 3 or more consecutive days. Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7. Example 1: Input: n = 2 Output: 8 Explanation: 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 3: Input: n = 10101 Output: 183236316 Constraints: 1 <= n <= 105

Explanation

Here's the breakdown of the solution:

• Dynamic Programming: The core idea is to use dynamic programming to build up the number of valid attendance records. We'll maintain states that track the length of the record, the number of absences used, and the number of consecutive late days.
• State Representation: The DP state will be defined as dp[i][j][k], where i is the length of the attendance record constructed so far, j is the number of absences used (0 or 1), and k is the number of consecutive late days (0, 1, or 2).

• Transitions: The transitions involve adding a 'P', 'L', or 'A' to the end of the existing record, updating the DP state accordingly, and ensuring the constraints are not violated.

• Time Complexity: O(n), Space Complexity: O(n)

Code

    def checkRecord(n: int) -> int:
    """
    Calculates the number of possible attendance records of length n that make a student eligible for an attendance award.

    Args:
        n: The length of the attendance record.

    Returns:
        The number of possible attendance records modulo 10^9 + 7.
    """

    MOD = 10**9 + 7
    dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]

    dp[0][0][0] = 1

    for i in range(1, n + 1):
        for j in range(2):
            for k in range(3):
                # Present
                dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD

                # Late
                if k < 2:
                    dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][j][k]) % MOD

                # Absent
                if j < 1:
                    dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i - 1][j][k]) % MOD

    total_records = 0
    for j in range(2):
        for k in range(3):
            total_records = (total_records + dp[n][j][k]) % MOD

    return total_records