Student Attendance Record II Problem


Description

LeetCode Problem 552.

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 10^9 + 7.

Example 1:

1
2
3
4
5
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:

1
2
Input: n = 1
Output: 3

Example 3:

1
2
Input: n = 10101
Output: 183236316

Constraints:

  • 1 <= n <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long int mod = 1e9 + 7;
    long long int dp[100001][2][3];
    
    int helper(int n, int absent, int late) { 
        if (late >= 3 || absent >= 2) 
            // not an eligible record condition 
            return 0; 
        if (n == 0) 
            // recurrence call till n == 0, i.e. we got an eligible record
            return 1; 
        
        //Memoization 
        if (dp[n][absent][late] != -1) 
        	return dp[n][absent][late];
        
        //Recurrence calls
        int p_selected = helper(n-1, absent, 0); // if we selected Present
        int a_selected = helper(n-1, absent + 1, 0); // if we selected Absent
        int l_selected = helper(n-1, absent, late + 1); // if we selected Late
        
        // Output = Sum of all three recurrence call outputs 
        return dp[n][absent][late] = (p_selected%mod + a_selected%mod + l_selected%mod ) % mod;
    }
    
    int checkRecord(int n) {
        //Initializing dp with -1
        memset(dp, -1, sizeof(dp));
        return helper(n, 0, 0);
    }
};




Related Posts

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...