Skip to content

552. Student Attendance Record II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 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
33
34
35
36
class Solution {
 public:
  int checkRecord(int n) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := length so far w/ i A's and the latest chars are j L's
    vector<vector<long>> dp(2, vector<long>(3));
    dp[0][0] = 1;

    while (n--) {
      const auto prev(dp);

      // Append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod;

      // Append L
      dp[0][1] = prev[0][0];

      // Append L
      dp[0][2] = prev[0][1];

      // Append A or append P
      dp[1][0] = (prev[0][0] + prev[0][1] + prev[0][2] +
                  prev[1][0] + prev[1][1] + prev[1][2]) % kMod;

      // Append L
      dp[1][1] = prev[1][0];

      // Append L
      dp[1][2] = prev[1][1];
    }

    return accumulate(begin(dp), end(dp), 0, [](int s, vector<long>& row) {
      return (s + accumulate(begin(row), end(row), 0L)) % kMod;
    });
  }
};

 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
33
34
35
class Solution {
  public int checkRecord(int n) {
    final int kMod = 1_000_000_007;
    // dp[i][j] := length so far w/ i A's and the latest chars are j L's
    long[][] dp = new long[2][3];
    dp[0][0] = 1;

    while (n-- > 0) {
      long[][] prev = Arrays.stream(dp)
                          .map((long[] A) -> A.clone())
                          .toArray((int length) -> new long[length][]);

      // Append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod;

      // Append L
      dp[0][1] = prev[0][0];

      // Append L
      dp[0][2] = prev[0][1];

      // Append A or append P
      dp[1][0] =
          (prev[0][0] + prev[0][1] + prev[0][2] + prev[1][0] + prev[1][1] + prev[1][2]) % kMod;

      // Append L
      dp[1][1] = prev[1][0];

      // Append L
      dp[1][2] = prev[1][1];
    }

    return (int) ((dp[0][0] + dp[0][1] + dp[0][2] + dp[1][0] + dp[1][1] + dp[1][2]) % kMod);
  }
}

 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
class Solution:
  def checkRecord(self, n: int) -> int:
    kMod = 1_000_000_007
    # dp[i][j] := length so far w/ i A's and the latest chars are j L's
    dp = [[0] * 3 for _ in range(2)]
    dp[0][0] = 1

    for _ in range(n):
      prev = [A[:] for A in dp]

      # Append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod

      # Append L
      dp[0][1] = prev[0][0]

      # Append L
      dp[0][2] = prev[0][1]

      # Append A or append P
      dp[1][0] = (prev[0][0] + prev[0][1] + prev[0][2] +
                  prev[1][0] + prev[1][1] + prev[1][2]) % kMod

      # Append L
      dp[1][1] = prev[1][0]

      # Append L
      dp[1][2] = prev[1][1]

    return (sum(dp[0]) + sum(dp[1])) % kMod