Can anyone solve this problem not using brute force? I'm so happy if somebody can help me.

A beautiful bit string is a string which can be described as a right bracket string, and lexicography order not larger than all of its bracket-circle-permutation. For example: 111000 -> ((())) is a beautiful string (110001 -> (()))( is not a right permutation), but 101 -> ()( is not, and 110010 is also not, because 110010 > 101100 and 101100 -> ()(()) is a bracket-circle-permutation of 110010.

(I have changed the problem set, this is my original problem, I realize that the last one I wrote is not enough to solve my original one.)

Count the number of beautiful strings with n bit. And let a n-bit beautiful string, count the number of beautiful strings which have lexicography order smaller than this. Of course, n is even.

• When solving this problem: http://www.codechef.com/problems/MARCHA6, I got an issue, that is: Let 2 binary strings A and B. With every index i of string A, calculate the max matching of string starting from i and string B. For example:
• A= 1 0 1 1 0 0 1 1 1 0
• B= 0 1 1 1 0 1
• with i= 1 -> max matching= 0
• i= 2 -> max matching= 3 (it is '0 1 1')
• i= 3 -> max matching= 0
• i= 4 -> max matching= 0
• i= 5 -> max matching= 1 (it is '0')
• Could anyone tell me how to solve it in O(n)?

• Thank you! Sorry for my poor English.