Let’s look at another SPOJ problem today, called Square Brackets. The problem is how many proper bracket expressions can be made having a certain length. For added measure, you are given the placement of a few opening brackets (which is trivial to handle, as you’ll see).

For our example, we have an expression with length of six (so, three bracket pairs) and the third place is given as an opening bracket:

. . [ . . .

So, how many expressions can be made from that above?

My first thought is, uh oh, traverse all permutations, branch at each place in the expression, generate all options and bubble them up to the top. And yes, if we were required to print all proper expressions, this would be required. Fortunately, though, we’re asked only for the proper expression count, and this lets us take a nice shortcut.

What’s the trick? Well, before we start, we’re at bracket depth 0, and when we end, we better be at bracket depth 0 (otherwise, the expression can’t be considered proper). So, we simply keep track of how many branches are at a particular depth, and “branch” at each place by moving our counts around like tokens.

It’s easier to show you with a picture for our example:

Moves at each expression place

0: Before we start, we have a count of 1 at depth 0.

1: Open/close, can only open though (proper expression can’t have negative depth), count 1 at depth 1.

2: Open/close, branch, depth 1 goes to both depth 0 (i.e. close) and 2 (i.e. open).

3. Open only, depth 0 goes to depth 1, depth 2 goes to depth 3

4. Open/close, depth 1 branches to 0 and 2, depth 3 branches to 2 but 4 isn’t valid (since the expression can never close at that depth)

5. Open/close, depth 0 to depth 1, depth 2 to depth 1 and 3.

6. Open/close, depth 1 to depth 0, etc.

After the expression is processed, our answer is in the final place of the 0-depth column. Our answer for this example is three.

General Algorithm

  expression = array[1..num_pairs*2], each item is array[-1,1] // open/close
  each open expression item is array [1] // open only
 
  depth_counts = array[0..num_pairs]
  depth_counts[0] = 1 // to start
 
   for each expression item as depth_changes // loop: O(num_pairs)
 
    depth_counts_past = depth_counts
    depth_counts = array[0..num_pairs]
    for each depth_counts_past index as count // loop: O(num_pairs)
 
      for each depth_changes as depth_change // loop: O(2)
        next_count = count + depth_change
        if next_count >= 0 and next_count <= num_pairs
          depth_counts[next_count] += depth_counts_past[count]
        end if
      end for each
    end for each
  end for each
 
  result = depth_counts[0]

And there we are. What is inherently a permutation problem has been collapsed into complexity O(N²). Calculating the answer for 500 bracket pairs with ruby takes under one second on my system, and the result is a number having 300 places. Not bad!