static final int M = 1000000007;
public int checkRecord(int n) {
long[] PorL = new long[n + 1]; // ending with P or L, no A
long[] P = new long[n + 1]; // ending with P, no A
PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;
for (int i = 2; i <= n; i++) {
P[i] = PorL[i  1];
PorL[i] = (P[i] + P[i  1] + P[i  2]) % M;
}
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n1)length strings
long s = (PorL[i] * PorL[n  i  1]) % M;
res = (res + s) % M;
}
return (int) res;
}
Simple Java O(n) solution


the following is my understanding for your code, if wrong, pls correct me:
P[i] = PorL[i  1]; //this line means ending with P, just appending P in PorL
PorL[i] = (P[i] + P[i  1] + P[i  2]) % M; //P[i] end with P, P[i1], end with one L(or PL), P[i2], end with two L(or LL).and last logic ,res init value with PorL without A, and add one A to the sequence.
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n1)length strings
long s = (PorL[i] * PorL[n  i  1]) % M;
res = (res + s) % M;
}
very nice and clean solution.

@vincexu You cannot use it.
Because it will miss some situations like ".LLL.", which are correct after inserting an A into it.