Student Attendance Record II - Practice Coding Problems

Student Attendance Record II - Problem

Dynamic Programming Hard

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 10^9 + 7.

Input & Output

Example 1 — Small Case

$ Input: n = 2

› Output: 8

💡 Note: Valid records: PP, PL, PA, LP, LL, LA, AP, AL. Invalid: AA (2 absences), no records with LLL since n=2.

Example 2 — Single Day

$ Input: n = 1

› Output: 3

💡 Note: All single-character records are valid: A, L, P. None violate the constraints.

Example 3 — Larger Case

$ Input: n = 10101

› Output: 183236316

💡 Note: For large n, the number of valid records grows exponentially but must be computed modulo 10^9 + 7.

Constraints

1 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Length n of attendance record

Constraints

< 2 absences, no 3+ consecutive late days

Output

Count of valid records modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Track state as (absences, consecutive_late) to ensure constraints while building records

Asked in

G Google 15 M Microsoft 8

The key insight is to track three states: position, total absences, and consecutive late days. We can use dynamic programming to build valid records day by day. The optimal approach uses space-optimized DP with rolling arrays. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Recursion with Memoization	O(n)	O(n)	Cache recursive results to avoid recalculating same states
2D Dynamic Programming	O(n)	O(n)	Build table tracking absences and consecutive late days
Space-Optimized DP	O(n)	O(1)	Use only current and previous states to save memory
Recursive Brute Force	O(3ⁿ)	O(n)	Generate all possible attendance strings and count valid ones

Recursion with Memoization — Algorithm Steps

Define state as (position, absences, consecutive_late)
Use memoization to cache computed results
For each state, try adding A, L, or P

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Track (position, absences, consecutive_late)

Cache

Store result for each unique state

Reuse

Return cached result when state repeats

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MOD = 1000000007;
static int memo[100001][2][3];
static int initialized = 0;

int dp(int pos, int absences, int consecutiveLate, int n) {
    if (consecutiveLate >= 3 || absences >= 2) {
        return 0;
    }
    if (pos == n) {
        return 1;
    }
    
    if (memo[pos][absences][consecutiveLate] != -1) {
        return memo[pos][absences][consecutiveLate];
    }
    
    long long result = 0;
    // Try adding 'A'
    result = (result + dp(pos + 1, absences + 1, 0, n)) % MOD;
    // Try adding 'L'
    result = (result + dp(pos + 1, absences, consecutiveLate + 1, n)) % MOD;
    // Try adding 'P'
    result = (result + dp(pos + 1, absences, 0, n)) % MOD;
    
    memo[pos][absences][consecutiveLate] = result;
    return result;
}

int solution(int n) {
    if (!initialized) {
        memset(memo, -1, sizeof(memo));
        initialized = 1;
    }
    return dp(0, 0, 0, n);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each of the O(n) unique states is computed once

✓ Linear Growth

Space Complexity

O(n)

Memoization table and recursion stack both take O(n) space

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursion with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler