Student Attendance Record II

Hard
1253.

Student Attendance Record II

Student Attendance Record II is a hard coding problem on dynamic programming and combinatorics, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var checkRecord = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. 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?

  2. Hint 2

    Only two facts matter: how many As so far (0 or 1) and how many Ls the prefix ends with (0, 1 or 2). That is six states.

  3. Hint 3

    From each state: P resets the late run, L extends it (allowed only below 2), A resets the run and is allowed only with 0 absences. Roll the six counts forward n times, reducing modulo 10^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

  1. Let dp[a][l] be the number of valid prefixes of the current length with a absences (0 or 1) that end in exactly l consecutive Ls (0, 1 or 2). Start with the empty record: dp[0][0] = 1.
  2. For each of the n positions compute the next table: appending P sends every dp[a][l] to next[a][0]; appending L sends dp[a][l] to next[a][l+1] when l < 2; appending A sends every dp[0][l] to next[1][0].
  3. 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].
  4. Reduce every entry modulo 10^9 + 7. After n steps return the sum of all six entries modulo 10^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 — an A or a P resets the run, not just P.
  • Sums of three or six residues exceed 32 bits: accumulate in 64-bit integers before reducing.
  • Enumerating records directly is 3^n — hopeless beyond n ≈ 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) % MOD

Java

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