Last updated on January 17th, 2025 at 01:11 am
Here, we see a Student Attendance Record II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Level of Question
Hard
Student Attendance Record II LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Dynamic Programming (DP). The problem involves breaking down the solution into overlapping subproblems and solving them using memoization or iterative DP.
3. Code Implementation in Different Languages
3.1 Student Attendance Record II C++
class Solution {
public:
int checkRecord(int n) {
long i;
long a0, a1, a2, a3;
long p0, p1, p2;
long l0, l1, l2;
ulong m = 1000000007;
if(n == 1) return 3;
if(n == 2) return 8;
a3 = 1;
a2 = 1;
a1 = 2;
p2 = 1;
p1 = 3;
l1 = 3;
for(i=3; i<=n; i++){
p0 = (a1 + p1 + l1)%m;
a0 = (a1 + a2 + a3)%m;
l0 = (p1 + a1 + p2 + a2)%m;
p2 = p1%m;
p1 = p0%m;
a3 = a2%m;
a2 = a1%m;
a1 = a0%m;
l1 = l0%m;
}
return (a0 + p0 + l0)%m;
}
};3.2 Student Attendance Record II Java
class Solution {
private int mod= 1000000007;
int dp[][][] = new int[100002][2][3];
public int solve(int ind,int n,int cnt_abs,int cnt_late)
{
if(ind >= n)
return 1;
if(dp[ind][cnt_abs][cnt_late]!=-1)
return dp[ind][cnt_abs][cnt_late];
int abs= cnt_abs==0?solve(ind+1,n,1,0):0;
int pre = solve(ind+1,n,cnt_abs,0);
int late=0;
if(cnt_late!=2)
late=solve(ind+1,n,cnt_abs,cnt_late+1);
return dp[ind][cnt_abs][cnt_late]=((pre+late)%mod+abs)%mod;
}
public int checkRecord(int n) {
for (int i = 0; i < 100002; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 3; k++) {
dp[i][j][k] = -1;
}
}
}
return solve(0,n,0,0);
}
}
3.3 Student Attendance Record II JavaScript
let mod = 1e9 + 7;
function fn(n, i, j, res) {
if (n === 0) return 1;
if (res[n][i][j] !== mod) return res[n][i][j];
let val1 = 0, val2 = 0, val3 = 0;
if (i > 0) val1 = fn(n - 1, i - 1, 2, res) % mod;
if (j > 0) val2 = fn(n - 1, i, j - 1, res) % mod;
val3 = fn(n - 1, i, 2, res) % mod;
return res[n][i][j] = ((val1 % mod + val2 % mod) % mod + val3 % mod) % mod;
}
var checkRecord = function (n) {
let i = 1, j = 2, res = [];
for (let i = 0; i <= n; i++) {
let arr = [];
for (let i = 0; i <= 1; i++) arr.push(new Array(3).fill(mod));
res.push(arr);
}
return fn(n, i, j, res);
};
3.4 Student Attendance Record II Python
class Solution(object):
def checkRecord(self, n):
MOD = 10**9 + 7
ax = x = xl = 1
axl = axll = xll = 0
for _ in range(n-1):
ax, axl, axll, x, xl, xll = (ax + x + xl + axl + axll + xll) % MOD, ax, axl, (x + xl + xll) % MOD, x, xl
return (ax + x + xl + axl + axll + xll) % MOD
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(1) |