Student Attendance Record II

hard dp

Problem

Count length-n records over {A, L, P} that are 'eligible' (≤1 A and never 3 consecutive L), mod 1e9+7.

Inputn = 2

Output8

Six transitions: at each i, choose P/L/A subject to constraints; total = sum over final states.

def check_record(n):
    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(n):
        for a in range(2):
            for l in range(3):
                v = dp[i][a][l]
                if not v: continue
                dp[i+1][a][0] = (dp[i+1][a][0] + v) % MOD
                if a == 0: dp[i+1][1][0] = (dp[i+1][1][0] + v) % MOD
                if l < 2: dp[i+1][a][l+1] = (dp[i+1][a][l+1] + v) % MOD
    return sum(dp[n][a][l] for a in range(2) for l in range(3)) % MOD

function checkRecord(n) {
  const MOD = 1_000_000_007n;
  const dp = Array.from({ length: n + 1 }, () => Array.from({ length: 2 }, () => new Array(3).fill(0n)));
  dp[0][0][0] = 1n;
  for (let i = 0; i < n; i++)
    for (let a = 0; a < 2; a++)
      for (let l = 0; l < 3; l++) {
        const v = dp[i][a][l];
        if (!v) continue;
        dp[i+1][a][0] = (dp[i+1][a][0] + v) % MOD;
        if (a === 0) dp[i+1][1][0] = (dp[i+1][1][0] + v) % MOD;
        if (l < 2) dp[i+1][a][l+1] = (dp[i+1][a][l+1] + v) % MOD;
      }
  let s = 0n;
  for (let a = 0; a < 2; a++) for (let l = 0; l < 3; l++) s = (s + dp[n][a][l]) % MOD;
  return Number(s);
}

class Solution {
    public int checkRecord(int n) {
        long MOD = 1_000_000_007L;
        long[][][] dp = new long[n + 1][2][3];
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int a = 0; a < 2; a++)
                for (int l = 0; l < 3; l++) {
                    long v = dp[i][a][l];
                    if (v == 0) continue;
                    dp[i+1][a][0] = (dp[i+1][a][0] + v) % MOD;
                    if (a == 0) dp[i+1][1][0] = (dp[i+1][1][0] + v) % MOD;
                    if (l < 2) dp[i+1][a][l+1] = (dp[i+1][a][l+1] + v) % MOD;
                }
        long s = 0;
        for (int a = 0; a < 2; a++) for (int l = 0; l < 3; l++) s = (s + dp[n][a][l]) % MOD;
        return (int) s;
    }
}

int checkRecord(int n) {
    const long MOD = 1000000007;
    vector>> dp(n + 1, vector>(2, vector(3, 0)));
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int a = 0; a < 2; a++)
            for (int l = 0; l < 3; l++) {
                long v = dp[i][a][l];
                if (!v) continue;
                dp[i+1][a][0] = (dp[i+1][a][0] + v) % MOD;
                if (a == 0) dp[i+1][1][0] = (dp[i+1][1][0] + v) % MOD;
                if (l < 2) dp[i+1][a][l+1] = (dp[i+1][a][l+1] + v) % MOD;
            }
    long s = 0;
    for (int a = 0; a < 2; a++) for (int l = 0; l < 3; l++) s = (s + dp[n][a][l]) % MOD;
    return (int) s;
}

Explanation

We count length-n strings over {A, L, P} that stay eligible: at most one A overall, and never three Ls in a row. Rather than generate strings, we count by tracking just enough about the prefix we've built: how many As used and the current trailing L-streak.

So dp[i][a][l] is the number of valid records of length i with a absences (0 or 1) and a current run of l trailing Ls (0, 1, or 2). We seed dp[0][0][0] = 1 — the empty record.

From every reachable state we append one of three letters. Adding P resets the L-streak to 0 (dp[i+1][a][0]). Adding A is allowed only if a == 0, moving to a = 1 and resetting L. Adding L is allowed only while l < 2, bumping the streak to l+1. Every count is taken mod 1e9+7.

Example: for n = 2 the valid strings number 8 — summing the final layer over all a and l states gives exactly that.

The answer adds up all dp[n][a][l]. Since there are only 6 (a,l) states per length, the whole thing is linear, O(n).

Time: O(n) Space: O(n)