Student attendance record ii

Dynamic Programming

56.4% acceptance

Jan 13, 2026

2361

290

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 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn check_record(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // dp[a][l] = count of valid sequences with a absences and l trailing lates
    // a in {0,1}, l in {0,1,2}
    let mut dp = [[0i64; 3]; 2];
    dp[0][0] = 1;
    for _ in 0..n {
      let mut ndp = [[0i64; 3]; 2];
      for a in 0..2usize {
        for l in 0..3usize {
          if dp[a][l] == 0 { continue; }
          let v = dp[a][l];
          // add 'P'
          ndp[a][0] = (ndp[a][0] + v) % MOD;
          // add 'L'
          if l < 2 {
            ndp[a][l + 1] = (ndp[a][l + 1] + v) % MOD;
          }
          // add 'A'
          if a == 0 {
            ndp[1][0] = (ndp[1][0] + v) % MOD;
          }
        }
      }
      dp = ndp;
    }
    let mut ans = 0i64;
    for a in 0..2 { for l in 0..3 { ans = (ans + dp[a][l]) % MOD; } }
    ans as i32
  }
}