# O(n) time O(1) space solution

• axly represents number of strings containing x A's and ending with y L's.

``````public class Solution {
long M = 1000000007;
public int checkRecord(int n) {
long a0l0 = 1, a0l1 = 0, a0l2 = 0, a1l0 = 0, a1l1 = 0, a1l2 = 0;
for (int i = 0; i <= n; i++) {
long a0l0_ = (a0l0 + a0l1 + a0l2) % M;
a0l2 = a0l1;
a0l1 = a0l0;
a0l0 = a0l0_;
long a1l0_ = (a0l0 + a1l0 + a1l1 + a1l2) % M;
a1l2 = a1l1;
a1l1 = a1l0;
a1l0 = a1l0_;
}
return (int) a1l0;
}
}``````

• Could you explain how this works?

• @vinod23 For a1l0, why don't we add a0l1 and a0l2, for which we can add 1 ‘a' at current position?

• @vinod23 This solution leads to incorrect answers. You're only returning solutions with 1 'A' and forgetting about solutions with no 'A's.

• @ayush201 But it is accpted……

• @fangyan I tried running it. It doesn't lead to the correct answer. Try it yourself.

• @ayush201 eh, I tried......it is accepted....haha, a little strange. I think I understand it

• @ayush201 sorry, I change the < sign to <= sign in the for loop, I forgot it just now.

• @ayush201 @fangyan
I think maybe you guys don't fully understand @vinod23 's solution, both of you. Although there is a minor error here (should change `for (int i = 0; i < n; i++)` into `for (int i = 0; I <= n; i++)`). Let me explain why to see if it can help.

For @fangyan 's question, since we have `long a0l0_ = (a0l0 + a0l1 + a0l2) % M;` before we update `a1l0`, surely we do NOT need to add `a0l1` and `a0l2` again, cause `a0l0` has already included them when calculate `a1l0`.

For @ayush201 's question, the solution is "correct" indeed (after fix the minor error). The secret why change `i<n` into `i<=n` can help is the last line `return (int) a1l0;`. Read the code carefully and we can see that `a1l0` equals the total sum of `(a0l0, a0l1, a0l2, a1l0, a1l1, a1l2)` in each loop. Thus we should add one more loop for `i == n`.

• @jakobcornell For detailed explanation you can see the problem editorial. Thanks.

• @ayush201 Sorry I have corrected it now.

• @realisking Yes. Thanks for your explanation~

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