package com.fishercoder.solutions;

/**
 * 552. Student Attendance Record II
 *
 * Given a positive integer n, return the number of all possible attendance records with length n,
 * which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.

 A student attendance record is a string that only contains the following three characters:

 'A' : Absent.
 'L' : Late.
 'P' : Present.

 A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

 Example 1:

 Input: n = 2
 Output: 8

 Explanation:
 There are 8 records with length 2 will be regarded as rewardable:
 "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
 Only "AA" won't be regarded as rewardable owing to more than one absent times.

 Note: The value of n won't exceed 100,000.
 */
public class _552 {

    /**credit: https://discuss.leetcode.com/topic/86526/improving-the-runtime-from-o-n-to-o-log-n*/
    public int checkRecord(int n) {
        final int MOD = 1000000007;
        int[][][] f = new int[n + 1][2][3];

        f[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    int val = f[i - 1][j][2]; // ...P
                    if (j > 0) {
                        val = (val + f[i - 1][j - 1][2]) % MOD; // ...A
                    }
                    if (k > 0) {
                        val = (val + f[i - 1][j][k - 1]) % MOD; // ...L
                    }
                    f[i][j][k] = val;
                }
            }
        }
        return f[n][1][2];
    }

}

@@ -860,19 +860,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -1009,15 +1009,29 @@
 og-n
-*/%0A
+%0A         */%0A   
     
+ 
 publ
@@ -1066,16 +1066,20 @@
         
+    
 final in
@@ -1098,16 +1098,20 @@
 000007;%0A
+    
         
@@ -1155,16 +1155,20 @@
         
+    
 f%5B0%5D = n
@@ -1201,32 +1201,36 @@
 1, 1%7D%7D;%0A        
+    
 for (int i = 1; 
@@ -1248,32 +1248,36 @@
 ) %7B%0A            
+  
+  
 for (int j = 0; 
@@ -1286,24 +1286,28 @@
 %3C 2; j++) %7B%0A
+    
             
@@ -1360,16 +1360,20 @@
         
+   
+ 
 int val 
@@ -1414,24 +1414,28 @@
             
+    
 if (j %3E 0) %7B
@@ -1427,32 +1427,36 @@
    if (j %3E 0) %7B%0A
+    
                 
@@ -1523,34 +1523,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1590,32 +1590,36 @@
                 
+ 
+   
 val = (val + f%5Bi
@@ -1662,34 +1662,41 @@
                 
-%7D%0A
+    %7D%0A   
                 
@@ -1699,16 +1699,17 @@
         
+ 
 f%5Bi%5D%5Bj%5D%5B
@@ -1726,34 +1726,42 @@
                 
-%7D%0A
+    %7D%0A    
             %7D%0A  
@@ -1758,34 +1758,42 @@
       %7D%0A        
-%7D%0A
+    %7D%0A    
         return f
@@ -1803,16 +1803,26 @@
 %5B1%5D%5B2%5D;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 552