LeetCode 552: Student Attendance Record II Solution

Master LeetCode problem 552 (Student Attendance Record II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

552. Student Attendance Record II

Hard

Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can define two states: the number of days passed n and the number of 'A's encountered aCount. We can also keep track of the number of consecutive 'L's encountered lCount.

We can initialize a 3D array dp where dp[n][aCount][lCount] represents the number of valid attendance records of length n with aCount 'A's and ending with lCount consecutive 'L's.

We can then iterate through the possible states based on the current character being 'P', 'A', or 'L' and update the values in the dp array accordingly.

The final answer will be the sum of all valid attendance records for n days with less than 2 'A's and no more than 2 consecutive 'L's.

Time Complexity

The time complexity of this solution is O(n) where n is the input number of days.

Space Complexity

The space complexity of this solution is O(n) where n is the input number of days.

Solution Code

class Solution {
    public int checkRecord(int n) {
        int mod = 1000000007;
        long[][][] dp = new long[n + 1][2][3];
        dp[0][0][0] = 1;

        for (int i = 1; i <= n; i++) {
            // Ending with 'P'
            for (int a = 0; a <= 1; a++) {
                for (int l = 0; l <= 2; l++) {
                    dp[i][a][0] = (dp[i][a][0] + dp[i - 1][a][l]) % mod;
                }
            }

            // Ending with 'A'
            for (int l = 0; l <= 2; l++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][l]) % mod;
            }

            // Ending with 'L'
            for (int a = 0; a <= 1; a++) {
                for (int l = 1; l <= 2; l++) {
                    dp[i][a][l] = (dp[i][a][l] + dp[i - 1][a][l - 1]) % mod;
                }
            }
        }

        long sum = 0;
        for (int a = 0; a <= 1; a++) {
            for (int l = 0; l <= 2; l++) {
                sum = (sum + dp[n][a][l]) % mod;
            }
        }

        return (int) sum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 552 (Student Attendance Record II)?

This page provides optimized solutions for LeetCode problem 552 (Student Attendance Record II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 552 (Student Attendance Record II)?

The time complexity for LeetCode 552 (Student Attendance Record II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 552 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 552 in Java, C++, or Python.

Back to LeetCode Solutions