class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
a = 0
for c in s:
if c == 'A':
a += 1
if a > 1:
return False
if s.find('LLL') != -1:
return False
return True


a0/(a1/a2/.../an-1)

class Solution(object):
def optimalDivision(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
def dfs(cur):
if len(cur) == 1:
yield cur[0], str(cur[0])
elif len(cur) == 2:
yield float(cur[0])/cur[1], '{}/{}'.format(cur[0], cur[1])
else:
x = float(cur[0])
for n in cur[1:]:
x /= n
s = '/'.join(map(str, cur))
yield x, s
for i in xrange(1, len(cur)):
left = cur[:i]
right = cur[i:]
for xl, sl in dfs(left):
for xr, sr in dfs(right):
x = float(xl) / float(xr)
if len(left) > 1:
sl = '({})'.format(sl)
if len(right) > 1:
sr = '({})'.format(sr)
s = '{}/{}'.format(sl, sr)
yield x, s

ans = ''
m = 0.0
for x, s in dfs(nums):
if x > m:
m = x
ans = s

return ans


class Solution(object):

def optimalDivision(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
if len(nums) == 1:
return str(nums[0])
elif len(nums) == 2:
return '{}/{}'.format(nums[0], nums[1])
else:
return '{}/({})'.format(nums[0], '/'.join(map(str, nums[1:])))


class Solution(object):

def splitLoopedString(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
pool = []
for i, s in enumerate(strs):
strs[i] = max(s, s[::-1])

def to_right(s, i, j):
ans = s[j:]
for k in xrange(1, len(strs)):
t = (i+k) % len(strs)
ans += strs[t]
ans += s[:j]
return ans

mc = max(''.join(strs))
for i, s in enumerate(strs):
for j, c in enumerate(s):
if c == mc:
pool.append(to_right(s, i, j))
s = s[::-1]
for j, c in enumerate(s):
if c == mc:
pool.append(to_right(s, i, j))

return max(pool)


f(n) = f(n-1) + f(n-2) + f(n-3)

S = sum{f(i)*f(n-1-i): i = 0, 1, ..., n-1}

class Solution(object):
def checkRecord(self, n):
"""
:type n: int
:rtype: int
"""
f = [0] * max((n+1), 4)
f[0] = 1
f[1] = 2
f[2] = 4
f[3] = 7
for i in xrange(4, n+1):
f[i] = (f[i-1]+f[i-2]+f[i-3]) % (10**9+7)
ans = f[n]
for i in xrange(n):
ans = (ans + f[i] * f[n-1-i]) % (10**9+7)
return ans