I have used the same program which was given in the problem..
By Just using a count and checking the input string..
i got the value..
But still i am getting TLE

Is there anyway in which i can optimise it??

Your program works with O(n!) time: of course, it's TL.
Find the rule in which the next one is got.