Student Attendance Record II

Student Attendance Record II

What is this problem about?

"Student Attendance Record II" is the significantly harder follow-up to the first problem. You are asked to find the total number of possible attendance strings of length n that would be eligible for an award. Since the number can be very large, you must return it modulo 10^9 + 7. The eligibility rules remain: fewer than 2 'A's and no 3 consecutive 'L's. This is no longer a validation problem; it's a counting problem.

Why is this asked in interviews?

This is a classic "Hard" dynamic programming problem asked by companies like Sprinklr and Google. It tests your ability to define complex DP states and identify transitions. Because n can be large, it also provides an opportunity for candidates to discuss optimization techniques like Matrix Exponentiation (which can solve this in O(log n) time). It separates candidates who can only do simple DP from those who can manage multiple interacting constraints.

Algorithmic pattern used

This problem uses Dynamic Programming with State Compression. The state needs to track three things:

1. The length of the string so far.
2. The total number of 'A's used (0 or 1).
3. The number of consecutive 'L's at the end of the string (0, 1, or 2). This gives us a DP table of size n x 2 x 3. The transitions involve adding 'P', 'A', or 'L' to the current state and seeing which new state we land in. For example, if we have one 'A' and two 'L's, we cannot add another 'L', but we can add 'P'.

Example explanation (use your own example)

For n=2, possible eligible strings are:

• "PP", "PL", "PA", "LP", "LL", "LA", "AP", "AL"
• Invalid strings: None for n=2 (since "AAA" or "LLL" need at least 3 characters). Wait, "AA" is invalid because it has two 'A's (the rule is fewer than 2). So for n=2:
• 0 'A's: "PP", "PL", "LP", "LL" (4)
• 1 'A': "PA", "AP", "AL", "LA" (4) Total = 8. The DP approach would calculate this by summing transitions from n=1.

Common mistakes candidates make

Failing to apply the modulo operation at every addition step is a very frequent error that leads to integer overflow. Another mistake is not correctly defining the state, such as forgetting to track the "total 'A's" separately from the "consecutive 'L's". Candidates also sometimes struggle with the base cases (n=0 or n=1) which are essential for the DP to work correctly.

Interview preparation tip

Practice defining the DP state clearly. Write down the transitions for each character ('P', 'A', 'L') explicitly:

• Adding 'P': Resets consecutive 'L's to 0, 'A' count stays same.
• Adding 'A': Resets consecutive 'L's to 0, 'A' count increases.
• Adding 'L': Increases consecutive 'L's by 1, 'A' count stays same. Being able to explain these transitions clearly to your interviewer is half the battle.