# O(n) constance space

• Calculate the number of each states base on previous result using a constant space rolling array

``````    private static final int BASE = 1000000007;
public int checkRecord(int n) {
int[][] tab = new int[2][3];
int[][] sumOfP = new int[2][3];
tab[0][0] = 1;
int prev = 0;
int curr = 1;
for (int i = 1; i <= n; i++) {
prev = (i-1) & 1;
curr = i & 1;
// curr0: end with P  -> PP + LP + LLP (prev0 + prev1 + prev2)
// curr1: end with L  -> PL (prev0)
// curr2: end with LL -> LL (prev1)
//                    -> LLL (invalid)
tab[curr][0] = ((tab[prev][0] + tab[prev][1]) % BASE + tab[prev][2]) % BASE;
tab[curr][1] = tab[prev][0];
tab[curr][2] = tab[prev][1];
// calculate how many P's are there, since each P can be exchanged with an A and got a new valid sequence
sumOfP[curr][0] = ((tab[curr][0] + sumOfP[prev][0]) % BASE + (sumOfP[prev][1] + sumOfP[prev][2]) % BASE) % BASE;
sumOfP[curr][1] = sumOfP[prev][0];
sumOfP[curr][2] = sumOfP[prev][1];
}
// calcualte the number of sequence with one 'A'
int sum = ((sumOfP[curr][0] + sumOfP[curr][1]) % BASE + sumOfP[curr][2]) % BASE;

return ((sum + tab[curr][0]) % BASE + (tab[curr][1] + tab[curr][2]) % BASE) % BASE;
}
``````

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