552. Student Attendance

Student Attendance Record II

A great exercise to practice bottom up style DP.

At its core, this problem is about how to legally "chain" records according to rules 🐲.

Read the Rules Carefully

Each student's daily attendance has three possible values:

"A" for Absent, "L" for Late, "P" for Present.

Here's the key: to earn attendance award, a student must satisfy both conditions:

1. Count of "A" is strictly less than 2
2. There must be no 3 consecutive "L"s

The problem asks: given a positive integer $n$ representing the length of an attendance record,

how many valid attendance sequences allow a student to earn award?

What the Rules Tell Us

I. "A" count strictly less than 2 means "A" can never appear or just once.

Our counting logic must first split on "whether an A has occurred", because once an "A" appears, even if all subsequent days are "P", that "A" can't be erased.

It's a bit like how a single act of infidelity leaves a permanent mark: never goes away.

II. The constraint of no 3 consecutive "L"s means whether today can be "L" depends on if previous two days were already back-to-back "L"s.

Only if there was no consecutive "LL" can today be an "L".

You've Probably Spotted the DP Transitions 🍷

1. "Never Had an A" State

The most straightforward once. Sequences that already have an "A" can never transition into "never had an A" state, because as noted, once absent, "A" sticks to the record forever.

So transitions for "no A yet" state are:

I. Count of length-$i$ sequences with no "A" yet, while ending in "P"

comes from all valid length of $(i - 1)$ sequences with no "A":

${}^{(0)} C_i^\text{P} = {}^{(0)} C_{i - 1}^\text{P} + {}^{(0)} C_{i - 1}^\text{L} + {}^{(0)} C_{i - 1}^\text{LL}$

${}^{(0)}$ means no "A" has occurred yet.

Superscripts P, L, LL indicate sequence tail.

The subscript indicates the attendance on day $i$.

As long as no "A" has occurred, any valid ending from the previous day ("P", "L", or "LL")

can transition into today's "P".

Note: "L" and "LL" are different. "L" means the previous day was "L",

but the day before that wasn't "L". "LL" means both of last two days were "L".

II. Count of length of $i$ sequences with no "A" yet, while ending in "L"

comes from length of $(i - 1)$ sequences with no "A", while ending in "P":

${}^{(0)} C_i^\text{L} = {}^{(0)} C_{i - 1}^\text{P}$

If yesterday ended in "L" and today is also "L", that becomes "LL", not "L".

III. Count of length of $i$ sequences with no "A" yet, while ending in "LL"

comes from length of $(i - 1)$ sequences with no "A", while ending in "L":

${}^{(0)} C_i^\text{LL} = {}^{(0)} C_{i - 1}^\text{L}$

An "LL" tail at the end of today means today is "L" and yesterday was also "L".

2. "Has Had an A" State

Pay closer attention here. The "has had an A" state can receive transitions from the "never had an A" state.

So our following four transitions require careful handling:

IV. Count of length of $i$ sequences with one "A", while ending in "P"

comes from all valid length of $(i - 1)$ sequences that already have one "A":

${}^{(1)} C_i^\text{P} = {}^{(1)} C_{i - 1}^\text{P} + {}^{(1)} C_{i - 1}^\text{L} + {}^{(1)} C_{i - 1}^\text{LL} + {}^{(1)} C_{i - 1}^\text{A}$

${}^{(1)}$ means exactly one "A" has occurred.

All valid sequences with one "A" from the previous day can transition via today's "P".

V. Count of length of $i$ sequences with one "A", while ending in "L"

comes from length of $(i - 1)$ sequences with one "A", while ending in "P" or "A":

${}^{(1)} C_i^\text{L} = {}^{(1)} C_{i - 1}^\text{P} + {}^{(1)} C_{i - 1}^\text{A}$

If yesterday ended in "P" or "A", today being late gives us such a transition.

VI. Count of length of $i$ sequences with one "A", while ending in "LL"

comes from length $(i - 1)$ sequences with one "A", while ending in "L":

${}^{(1)} C_i^\text{LL} = {}^{(1)} C_{i - 1}^\text{L}$

Yesterday ended in "L", and today is late again.

VII. Count of length of $i$ sequences with one "A", while ending in "A"

This means the sequence had no "A" until today, as the student was absent today 😏

Such a transition comes from all valid length of $(i - 1)$ sequences with no "A":

${}^{(1)} C_i^\text{A} = {}^{(0)} C_{i - 1}^\text{P} + {}^{(0)} C_{i - 1}^\text{L} + {}^{(0)} C_{i - 1}^\text{LL}$

3. Where Are the Base Cases?

Naturally, the case where only one day of attendance is counted.

So base cases have only three possible endings: "A", "L", "P":

${}^{(0)} C_1^\text{P} = {}^{(0)} C_1^\text{L} = 1, \quad {}^{(0)} C_1^\text{LL} = 0$

${}^{(1)} C_1^\text{P} = {}^{(1)} C_1^\text{L} = {}^{(1)} C_1^\text{LL} = 0, \quad {}^{(1)} C_1^\text{A} = 1$

4. A Small Observation

After writing out all seven transition equations, careful readers will notice:

I. At the end of yesterday, all valid sequences with no "A" yet

might get an "A" today via transition VII — all moving into the "one A, ending in A" state,

or stay as "no A" via transition I with today being "P".

II. Transitions III and VI are nearly identical.

Only difference is the superscript indicating whether an "A" has occurred.

III. Transitions II and V are quite similar as well.

Difference is that V must also consider sequences ending in "A" from previous day.

IV. Transitions IV and I are "full internal transfers".

In other words: if today is "P", you inherit all valid states from yesterday that carry the same number of "A"s as you do. That's "internal".

If Bottom Up Can Achieve $O(1)$ Space

There's no need to use recursive caching and incur $O(n)$ space complexity.

Pure bottom up also runs in $O(n)$ time complexity without any cache.

C++

#include <cmath>
#include <vector>
using namespace std;

int countPossibilities(int recordLen) // LeetCode Q.552.
{
    // Possible ends: "P", "L", "LL".
    long long noAbsEndP = 1, noAbsEndL = 1, noAbsEndLL = 0;

    // Possible ends: "P", "L", "LL", "A".
    long long oneAbsEndP = 0, oneAbsEndL = 0, oneAbsEndLL = 0, oneAbsEndA = 1;

    // Helper variables: help each day's branch counts update values.
    long long newNoAbsEndP = 0, newNoAbsEndL = 0, newNoAbsEndLL = 0;

    long long newOneAbsEndP = 0, newOneAbsEndL = 0, newOneAbsEndLL = 0, newOneAbsEndA = 0;

    long long modulo = pow(10, 9) + 7; // Long long prevents overflow.

    for (int day = 2; day <= recordLen; day++) {
        long long noAbsSum = noAbsEndP + noAbsEndL + noAbsEndLL;
        noAbsSum %= modulo;

        newNoAbsEndP = noAbsSum % modulo; // No.1: all 0 absence ends are now "P".

        newNoAbsEndL = noAbsEndP; // No.2: 0 absence end "P" => "L".
        newNoAbsEndLL = noAbsEndL; // No.3: 0 absence end "L" => "LL".

        long long oneAbsSum = oneAbsEndP + oneAbsEndL + oneAbsEndLL + oneAbsEndA;
        oneAbsSum %= modulo;

        newOneAbsEndP = oneAbsSum % modulo; // No.4: all 1 absence ends are now "P".

        // No.5: 1 absence end from "P" or "A" to "L".
        newOneAbsEndL = (oneAbsEndP + oneAbsEndA) % modulo;

        newOneAbsEndLL = oneAbsEndL; // No.6: 1 absence end "l" => "ll".

        newOneAbsEndA = noAbsSum % modulo; // No.7: from 0 to 1 absence.

        // Transit updated counts.
        noAbsEndP = newNoAbsEndP, noAbsEndL = newNoAbsEndL, noAbsEndLL = newNoAbsEndLL;

        oneAbsEndP = newOneAbsEndP, oneAbsEndL = newOneAbsEndL;
        oneAbsEndLL = newOneAbsEndLL, oneAbsEndA = newOneAbsEndA;

        // Reset helper variables for next day's usage.
        newNoAbsEndP = 0, newNoAbsEndL = 0, newNoAbsEndLL = 0;

        newOneAbsEndP = 0, newOneAbsEndL = 0, newOneAbsEndLL = 0, newOneAbsEndA = 0;
    }

    long long validCounts = (noAbsEndP + noAbsEndL + noAbsEndLL) % modulo;

    validCounts += (oneAbsEndP + oneAbsEndL + oneAbsEndLL + oneAbsEndA) % modulo;

    return validCounts % modulo;
}

Python

def count_possibilities(record_len: int) -> int:  # LeetCode Q.552.
    # Possible ends: "P", "L", "LL". Base case: record len = 1.
    no_abs_table = {"p": 1, "l": 1, "ll": 0}

    # Possible ends: "P", "L", "LL", "A". Base case: record len = 1.
    one_abs_table = {"p": 0, "l": 0, "ll": 0, "a": 1}

    # Help each day's tables update values.
    new_no_abs_table, new_one_abs_table = dict(), dict()

    modulo = 10 ** 9 + 7

    for _ in range(2, record_len + 1):
        
        no_abs_sum = sum(no_abs_table.values()) % modulo

        new_no_abs_table["p"] = no_abs_sum  # No.1: all 0 absence ends are now "P".

        new_no_abs_table["l"] = no_abs_table["p"]  # No.2: 0 absence end "P" => "L".
        new_no_abs_table["ll"] = no_abs_table["l"]  # No.3: 0 absence end "L" => "LL".

        one_abs_sum = sum(one_abs_table.values()) % modulo

        new_one_abs_table["p"] = one_abs_sum  # No.4: all 1 absence ends are now "P".

        # No.5: 1 absence end from "P" or "A" to "L".
        new_one_abs_table["l"] = (one_abs_table["p"] + one_abs_table["a"]) % modulo

        new_one_abs_table["ll"] = one_abs_table["l"]  # No.6: 1 absence end "l" => "ll".

        new_one_abs_table["a"] = no_abs_sum  # No.7: from 0 to 1 absence.

        no_abs_table.update(new_no_abs_table)
        one_abs_table.update(new_one_abs_table)
        
        new_no_abs_table.clear()  # Reset for next day's usage.
        new_one_abs_table.clear()
        
    valid_combinations = sum(no_abs_table.values()) + sum(one_abs_table.values())
    return valid_combinations % modulo

Since this problem doesn't involve absolute values, I use "abs" to represent "absence".

Remember to apply modulo periodically to prevent exploding large numbers.

Also, my variable recordLen/record_len is just LeetCode's parameter n.

Bottom up handles everything～～

Follow-up Problems

I. Intuitively, at the end of day 2, there shouldn't be any sequence with tail "LL" that has also had one absence.

Yet transition VI's code looks like this:

new_one_abs_table["ll"] = one_abs_table["l"] # No.6: 1 absence end "l" => "ll".

Why don't we need if statement to check whether we're on day 2 — with all results still correct? 😌

II. "LLL" disqualifies a student from the award. But "LLA", which is arguably worse, somehow doesn't eliminate the student — quite funny the game design is 🤡

Here's a question: if we want "LLA" to also disqualify a student, how should we modify transition equations?