# Share my thinking process - Finite State Machine

• A rewardable sequence can only have 6 states :
Either has Absence in previous sequence, we define it as hasA[i], or Not Absence, we define it as withoutA[i].
By each case, we can only have 0, 1, 2 continuous Late at the end of sequence.
By defining this 6 states, now we can draw all possible transitions. Each time we have 3 options, P, L, or A. The transition relationship is shown as following figure. Notice each time we take a P or A, we immediately end our L continuous record and go back to hasA[0] or withoutA[0].

Now the implementation is simply the translation of the figure. I attached both my first O(n) space version and the second optimized O(1) space version by observing that the current state only depends on last moment.

The time complexity is O(n).

``````public class Solution {

public int checkRecord(int n) {
long M = 1000000007;
// with i L at the end (i = 0, 1, 2)
long[][] hasA = new long[3][2];
long[][] withoutA = new long[3][2];

hasA[0][0] = 1; // 'A'
withoutA[0][0] = 1; // 'P'
withoutA[1][0] = 1; // 'L'
for (int i = 2; i <= n; i++) {
// only possible with 'P'
withoutA[0][(i + 1) % 2] = (withoutA[0][i % 2] + withoutA[1][i % 2] + withoutA[2][i % 2]) % M;
for (int j = 1; j <= 2; j++) {
// possible with 'L'
withoutA[j][(i + 1) % 2] = withoutA[j - 1][i % 2];
}
// possible with 'A' or 'P'
hasA[0][(i + 1) % 2] = (withoutA[0][(i + 1) % 2] + hasA[0][i % 2] + hasA[1][i % 2] + hasA[2][i % 2]) % M;
for (int j = 1; j <= 2; j++) {
// possible with 'L'
hasA[j][(i + 1) % 2] = hasA[j - 1][i % 2];
}
}

long res = 0;
for (int k = 0; k < 3; k++) {
res = (res + hasA[k][(n + 1) % 2] + withoutA[k][(n + 1) % 2]) % M;
}
return (int) res;
}

public int checkRecord2(int n) {
if (n == 1) return 3;
// with i L at the end (i = 0, 1, 2)
int[][] hasA = new int[3][n + 1];
int[][] withoutA = new int[3][n + 1];

hasA[0][1] = 1; // 'A'
withoutA[0][1] = 1; // 'P'
withoutA[1][1] = 1; // 'L'
for (int i = 2; i <= n; i++) {
// only possible with 'P'
withoutA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1];
for (int j = 1; j <= 2; j++) {
// possible with 'L'
withoutA[j][i] = withoutA[j - 1][i - 1];
}
// possible with 'A' or 'P'
hasA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1] + hasA[0][i - 1] + hasA[1][i - 1] + hasA[2][i - 1];
for (int j = 1; j <= 2; j++) {
// possible with 'L'
hasA[j][i] = hasA[j - 1][i - 1];
}
}

int res = 0;
for (int k = 0; k < 3; k++) {
res += hasA[k][n] + withoutA[k][n];
}
return res;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.