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
You should try to find some recurrence relation. Also this problem seems to be connected with Gray codes, but I hadn't used them in my solution. You also can find handfull next article about this algo