# Simple Java O(n) solution

• ``````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 (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}

return (int) res;
}
``````

• Nice solution.
I was trying to solve this problem in math way. However end up in this DP 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[i-1], end with one L(or PL), P[i-2], 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 (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}
very nice and clean solution.

• When inserting A into (n-1) length no-A string, can it be simplified to below line?

res = (res + n * PorL[n-1] ) % M;

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

• A very nice solution！

• clean and easy understanding solution!
I modified the PorL array to L array to separate the calculation of P and L:

``````    static final int mod = (int) (1e9+7);
public int checkRecord(int n){
long[] P = new long[n+1]; //end with P w/o A
long[] L = new long[n+1]; //end with L w/o A
P[0] = P[1] = L[1] = 1;
for(int i = 2; i <= n; i++){
P[i] = (P[i-1] + L[i-1]) % mod;
L[i] = (P[i-1] + P[i-2]) % mod;
}
long res = (P[n] + L[n]) % mod;
//insert A
for(int i = 0; i < n; i++){
long s = ((P[i] + L[i])%mod * (P[n-i-1] + L[n-i-1])%mod )% mod;
res = (res + s) % mod;
}
return (int) res;
}
``````

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