DEV Community

Cover image for 552. Student Attendance Record II
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

552. Student Attendance Record II

552. Student Attendance Record II

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

Example 1:

  • Input: n = 2
  • Output: 8
  • Explanation: There are 8 records with length 2 that are eligible for an award:

"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"

Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).

Example 2:

  • Input: n = 1
  • Output: 3

Example 3:

  • Input: n = 10101
  • Output: 183236316

Constraints:

  • 1 <= n <= 109

Solution:

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function checkRecord($n) {
        $kMod = 1000000007;
        $dp = array(array(0, 0, 0), array(0, 0, 0));
        $dp[0][0] = 1;

        while ($n-- > 0) {
            $prev = array_map(function($A) {
                return array_values($A);
            }, $dp);

            $dp[0][0] = ($prev[0][0] + $prev[0][1] + $prev[0][2]) % $kMod;

            $dp[0][1] = $prev[0][0];

            $dp[0][2] = $prev[0][1];

            $dp[1][0] = ($prev[0][0] + $prev[0][1] + $prev[0][2] + $prev[1][0] + $prev[1][1] + $prev[1][2]) % $kMod;

            $dp[1][1] = $prev[1][0];

            $dp[1][2] = $prev[1][1];
        }

        return (int)(($dp[0][0] + $dp[0][1] + $dp[0][2] + $dp[1][0] + $dp[1][1] + $dp[1][2]) % $kMod);

    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

Top comments (0)