# Why my solution got TLE? (AC now, O(n) time and O(1) space)

• I came up with the following DP solution where a, b, c, d, e, f, g represent the number of strings that
a: no A, end with one L
b: no A, end with LL
c: no A, end with P
d: one A, end with one L
e: one A, end with LL
f: one A, end with P
g: one A, end with A

``````class Solution(object):
def checkRecord(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 3
m = 10**9 + 7
a, b, c, d, e, f, g = 1, 1, 2, 1, 0, 1, 2
for _ in xrange(2, n):
# a, b, c, d, e, f, g = c, a, a+b+c, f+g, d, d+e+f+g, a+b+c
a, b, c, d, e, f, g = c, a, (a+b+c)% m, (f+g)% m, d, (d+e+f+g)% m, (a+b+c)% m
return (a+b+c+d+e+f+g) % m
``````

• Try this:

``````class Solution(object):
def checkRecord(self, n):
"""
:type n: int
:rtype: int
"""

# TLE solution
if n == 1:
return 3
m = 10**9 + 7
a, b, c, d, e, f, g = 1, 1, 2, 1, 0, 1, 2
for _ in xrange(2, n):
a, b, c, d, e, f, g = c, a, (a+b+c)% m, (f+g)% m, d, (d+e+f+g)% m, (a+b+c)% m
return (a+b+c+d+e+f+g) % m
``````

Just mod during the for loop.

• @fallcreek

Thanks! Can you please explain why this works if possible?

• @fungyh Keep number in range of int. Just a guess, if you don't mod your number during for loop, a, b, ... g will get very very large in the end, and cost more time during computation.

• @fallcreek
Thanks, I always thought mod is a slow operation :(

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