Student Attendance Record II

Problem Id: 552 Difficulty: Hard


Intuition

Solution


class Solution:
    def checkRecord(self, n: int) -> int:
        """
        no, one, two represent how many L at the end of s
        no[i] = no[i - 1] + one[i - 1] + two[i - 1]
        one[i] = no[i - 1]
        two[i] = one[i - 1]
        """
        # Edge case
        if n == 0:
            return 0

        # Prepare
        no = 1
        one, two, noa, onea, twoa = 0, 0, 0, 0, 0
        m = 10 ** 9 + 7

        # DP
        for i in range(1, n + 1):
            no, one, two, noa, onea, twoa = (
                (no + one + two) % m,
                no,
                one,
                (noa + no + one + two + onea + twoa) % m,
                noa,
                onea
            )
        return (no + one + two + noa + onea + twoa) % m