Student Attendance Record II — Problem & Solution
Student Attendance Record II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Student Attendance Record II is a hard coding problem on dynamic programming and combinatorics, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Combinatorics
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A bootcamp logs each learner's attendance as a string of n characters, one per session: 'A' (absent), 'L' (late) or 'P' (present).
A learner earns the perfect-attendance badge when both hold:
- they were absent fewer than 2 times in total, and
- they were never late 3 or more sessions in a row.
Given n, return how many of the 3^n possible records of length n earn the badge. The count is large, so return it modulo 10^9 + 7.
Example 1
Input: n = 2
Output: 8
Explanation: All nine records except `"AA"` qualify.
Example 2
Input: n = 4
Output: 43
Example 3
Input: n = 2026
Output: 906370326
Constraints
1 <= n <= 10^5
Hints for Student Attendance Record II
Hint 1
Build the record one character at a time. What do you need to remember about the prefix to know which characters may come next?
Hint 2
Only two facts matter: how many
As so far (0 or 1) and how manyLs the prefix ends with (0, 1 or 2). That is six states.Hint 3
From each state:
Presets the late run,Lextends it (allowed only below 2),Aresets the run and is allowed only with 0 absences. Roll the six counts forwardntimes, reducing modulo10^9 + 7, and sum them.
How to solve Student Attendance Record II
Whether a record can still be extended depends only on (absences so far, current run of trailing lates), which has six values — so count records with a six-state dynamic programme over the length.
Approach
- Let
dp[a][l]be the number of valid prefixes of the current length withaabsences (0 or 1) that end in exactlylconsecutiveLs (0, 1 or 2). Start with the empty record:dp[0][0] = 1. - For each of the
npositions compute the next table: appendingPsends everydp[a][l]tonext[a][0]; appendingLsendsdp[a][l]tonext[a][l+1]whenl < 2; appendingAsends everydp[0][l]tonext[1][0]. - So
next[0][0] = Σ dp[0][*],next[0][1] = dp[0][0],next[0][2] = dp[0][1],next[1][0] = Σ dp[0][*] + Σ dp[1][*],next[1][1] = dp[1][0],next[1][2] = dp[1][1]. - Reduce every entry modulo
10^9 + 7. Afternsteps return the sum of all six entries modulo10^9 + 7.
Why it works
The two badge rules only ever look at the total number of As and at the current run of Ls, and both are captured exactly by the state; every valid record of length k + 1 is a valid record of length k plus one allowed character, and each such extension is counted once. So the table counts every valid record exactly once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The late rule is about consecutive
Ls — anAor aPresets the run, not justP. - Sums of three or six residues exceed 32 bits: accumulate in 64-bit integers before reducing.
- Enumerating records directly is
3^n— hopeless beyondn ≈ 20.
Reference solution
Python
def checkRecord(n: int) -> int:
MOD = 10**9 + 7
a0l0, a0l1, a0l2, a1l0, a1l1, a1l2 = 1, 0, 0, 0, 0, 0
for _ in range(n):
s0 = (a0l0 + a0l1 + a0l2) % MOD
s1 = (a1l0 + a1l1 + a1l2) % MOD
a0l0, a0l1, a0l2, a1l0, a1l1, a1l2 = s0, a0l0, a0l1, (s0 + s1) % MOD, a1l0, a1l1
return (a0l0 + a0l1 + a0l2 + a1l0 + a1l1 + a1l2) % MODJava
public static int checkRecord(int n) {
final long MOD = 1000000007L;
long a0l0 = 1, a0l1 = 0, a0l2 = 0, a1l0 = 0, a1l1 = 0, a1l2 = 0;
for (int i = 0; i < n; i++) {
long s0 = (a0l0 + a0l1 + a0l2) % MOD;
long s1 = (a1l0 + a1l1 + a1l2) % MOD;
a1l2 = a1l1;
a1l1 = a1l0;
a1l0 = (s0 + s1) % MOD;
a0l2 = a0l1;
a0l1 = a0l0;
a0l0 = s0;
}
return (int) ((a0l0 + a0l1 + a0l2 + a1l0 + a1l1 + a1l2) % MOD);
}C++
int checkRecord(int n) {
const long long MOD = 1000000007LL;
long long a0l0 = 1, a0l1 = 0, a0l2 = 0, a1l0 = 0, a1l1 = 0, a1l2 = 0;
for (int i = 0; i < n; i++) {
long long s0 = (a0l0 + a0l1 + a0l2) % MOD;
long long s1 = (a1l0 + a1l1 + a1l2) % MOD;
a1l2 = a1l1;
a1l1 = a1l0;
a1l0 = (s0 + s1) % MOD;
a0l2 = a0l1;
a0l1 = a0l0;
a0l0 = s0;
}
return (int)((a0l0 + a0l1 + a0l2 + a1l0 + a1l1 + a1l2) % MOD);
}JavaScript
var checkRecord = function(n) {
var MOD = 1000000007;
var a0l0 = 1, a0l1 = 0, a0l2 = 0, a1l0 = 0, a1l1 = 0, a1l2 = 0;
for (var i = 0; i < n; i++) {
var s0 = (a0l0 + a0l1 + a0l2) % MOD;
var s1 = (a1l0 + a1l1 + a1l2) % MOD;
a1l2 = a1l1;
a1l1 = a1l0;
a1l0 = (s0 + s1) % MOD;
a0l2 = a0l1;
a0l1 = a0l0;
a0l0 = s0;
}
return (a0l0 + a0l1 + a0l2 + a1l0 + a1l1 + a1l2) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming