We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Student Attendance Record II

Number: 552

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a number n, count the number of possible attendance records of length n that make a student eligible for an award. A record is a string where the character 'A' represents Absent, 'L' represents Late, and 'P' represents Present. A record is eligible if it contains strictly fewer than 2 'A's and does not contain 3 or more consecutive 'L's. The answer should be returned modulo 10^9+7.

Key Insights

  • Use Dynamic Programming to simulate the sequence day by day.
  • Represent the state using the number of days processed, the count of 'A's used (0 or 1), and the current count of consecutive 'L's (0, 1, or 2).
  • For each day, consider adding a 'P', 'L', or 'A' while updating the state.
  • Only allow an 'A' if none has been used yet; only allow 'L' if the current consecutive count is less than 2.
  • Modular arithmetic is required at each step to prevent overflow.

Space and Time Complexity

Time Complexity: O(n) – We iterate through n days, and for each day we update a constant number of states. Space Complexity: O(n) if using a full DP table, but it can be optimized to O(1) since only the previous states are needed.

Solution

We solve the problem using a 3D dynamic programming approach where dp[i][a][l] represents the number of valid sequences of length i having used a number of 'A's and ending with l consecutive 'L's. The recurrence updates the dp table by considering three actions each day:

  • Append 'P': Resets consecutive 'L' count to 0.
  • Append 'L': Increments the consecutive 'L' count (ensuring it stays below 3).
  • Append 'A': Increases the absence count (allowed only if no 'A' has been used yet) and resets consecutive 'L' count. After processing n days, the answer is the sum of all valid states modulo 10^9+7.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with line-by-line comments.

MOD = 10**9 + 7

def checkRecord(n):
    # Create a DP table for states: days, absences (0 or 1), and consecutive lates (0 to 2)
    dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n+1)]
    dp[0][0][0] = 1  # Base state: 0 days, 0 absences, 0 consecutive lates
    
    for i in range(n):
        for a in range(2):  # a can be 0 or 1
            for l in range(3):  # l can be 0, 1, or 2
                if dp[i][a][l]:
                    # Option 1: Add 'P' which resets consecutive lates to 0
                    dp[i+1][a][0] = (dp[i+1][a][0] + dp[i][a][l]) % MOD
                    
                    # Option 2: Add 'L' if consecutive lates are less than 2
                    if l < 2:
                        dp[i+1][a][l+1] = (dp[i+1][a][l+1] + dp[i][a][l]) % MOD
                    
                    # Option 3: Add 'A' if no absence has been used yet
                    if a < 1:
                        dp[i+1][a+1][0] = (dp[i+1][a+1][0] + dp[i][a][l]) % MOD
                        
    # Sum all valid ending states after n days
    result = 0
    for a in range(2):
        for l in range(3):
            result = (result + dp[n][a][l]) % MOD
    return result

# Example usage:
print(checkRecord(2))  # Expected output: 8
← Back to All Questions