A balanced bracket sequence of length 2n is a string of n opening brackets ( and n closing brackets ) such that at every prefix the number of ( seen so far is at least the number of ) seen so far, and the two counts are equal at the very end. The nesting depth at any point is the current count of unmatched open brackets; the sequence's overall depth is the maximum depth reached at any prefix.
Given n and a maximum allowed depth d, count how many balanced bracket sequences of length 2n have depth never exceeding d at any point.
Line 1: two integers n and d.
A single integer: the count of balanced sequences of length 2n with depth always ≤ d.
Example 1
Input
2 1
Expected
1
Explanation
With n=2 and max depth 1, only "()()" stays within depth 1 the whole way through; "(())" is excluded because it briefly reaches depth 2, so the count is 1.
Example 2
Input
3 3
Expected
5
Explanation
With depth allowed up to 3 for n=3, every balanced sequence of length 6 qualifies (the 3rd Catalan number), giving a count of 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →