i don’t know why my solution is getting wrong… its a simple catalan problem …dont know where i screwed…plz help
def solve(n, k):
if (k > n - k):
k = n - k
res = 1
for i in range(k):
res = res * (n - i)
res = res // (i + 1)
return res
def catalan(n):
c = solve(2*n, n)
return c//(n + 1)
for _ in range(int(input())):
s=input()
l=len(s)
n=l-1
print(catalan(n)%1000000007)Your Code is correct. Actually the problem setter has added some extra-space after the sequence of characters in a line which is causing the error.
I tried your code with minor change and it’s working
Submission : CodeChef: Practical coding for everyone
P.S - It wasn’t your mistake.
yeah, i used strip() then it’s working fine for test cases
How do we know that the answer is the (n-1)th catalan number?
The nth catalan number gives us the total number of valid sequences of n left and n right parentheses.
But if we look at the sample test case given in the problem( i,e abcd),there are 5 ways.
But those 5 ways given in the problem seem different to me than what the definition of the 3rd catalan number(i.e c3) suggests.
Sorry if i missed something trivial (i m still a newbie 
).
Number of ways to insert n pairs of parentheses in a word of n+1 letters, e.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)). For n=3 there are 5 ways, ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd)))…
in the problem you need to insert n-1 pair of parenthesis in the string such that none of the parenthesis include a single char except the one covering the whole string