# Long and not elegant but easy to understand solution

• Run time should be O(n), but cannot pass the OJ with TLE. Will give the right answers.
'''
public int checkRecord(int n) {

``````    if(n == 0)return 0;
if(n == 1)return 3;
if(n == 2)return 8;
Map<String,Map<String,Long>> map = new HashMap<>();
Map<String,Long> NoA  = new HashMap<>();
NoA.put("pp", 1l);NoA.put("pl", 1l);NoA.put("lp",1l);NoA.put("ll", 1l);
Map<String, Long> A = new HashMap<>();
A.put("pp", 0l);A.put("pl", 0l);A.put("lp",0l);A.put("ll", 0l);
A.put("ap", 1l);A.put("pa", 1l);A.put("la",1l);A.put("al", 1l);
map.put("A", A);map.put("N", NoA);
for(long i = 2; i < n;i++){
Map<String,Long> tmpA = map.get("A");
Map<String,Long> tmpN = map.get("N");
long App = tmpA.get("pp") + tmpA.get("lp") + tmpA.get("ap");
long Npp = tmpN.get("pp") + tmpN.get("lp");
long Apl = tmpA.get("pp") + tmpA.get("lp") + tmpA.get("ap");
long Npl = tmpN.get("pp") + tmpN.get("lp");
long Alp = tmpA.get("pl") + tmpA.get("ll") + tmpA.get("al");
long Nlp = tmpN.get("pl") + tmpN.get("ll");
long All = tmpA.get("pl") + tmpA.get("al");
long Nll = tmpN.get("pl");
long Aap = tmpA.get("pa") + tmpA.get("la");
long Apa  = tmpN.get("pp") + tmpN.get("lp");
long Ala = tmpN.get("pl") + tmpN.get("ll");
long Aal = tmpA.get("pa") + tmpA.get("la");

tmpA.put("pp", App%1000000007);tmpA.put("pl", Apl%1000000007);tmpA.put("lp",Alp%1000000007);tmpA.put("ll", All%1000000007);
tmpA.put("ap", Aap%1000000007);tmpA.put("pa", Apa%1000000007);tmpA.put("la",Ala%1000000007);tmpA.put("al", Aal%1000000007);
tmpN.put("pp", Npp%1000000007);tmpN.put("pl", Npl%1000000007);tmpN.put("lp",Nlp%1000000007);tmpN.put("ll", Nll%1000000007);
map.put("A", tmpA);
map.put("N", tmpN);
}
long ans = 0;
Map<String,Long> tmpA = map.get("A");
Map<String,Long> tmpN = map.get("N");
for(String str : tmpA.keySet()){
ans += tmpA.get(str);
}
for(String str : tmpN.keySet()){
ans += tmpN.get(str);
}
System.out.println(ans);
return (int) (ans%1000000007);
``````

}
'''

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