Google codejam APAC Test practice round: Parentheses Order

Question

I spent one day solving this problem and couldn't find a solution to pass the large dataset.

Problem

An n parentheses sequence consists of n "("s and n ")"s.

Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.

For example, here are all valid 3 parentheses sequences in lexicographical order:

((()))

(()())

(())()

()(())

()()()

Given n and k, write an algorithm to give the k-th smallest sequence in lexicographical order.

For large data set: 1 ≤ n ≤ 100 and 1 ≤ k ≤ 10^18

Answer 1

This problem can be solved by using dynamic programming

• Let dp[n][m] = number of valid parentheses that can be created if we have n open brackets and m close brackets.
• Base case:
  dp[0][a] = 1 (a >=0)
• Fill in the matrix using the base case:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

Then, we can slowly build the kth parentheses.

• Start with a = n open brackets and b = n close brackets and the current result is empty

  while(k is not 0):
       If number dp[a][b] >= k: 
              If (dp[a - 1][b] >= k) is true:
                 * Append an open bracket '(' to the current result
                 * Decrease a 
              Else:
                 //k is the number of previous smaller lexicographical parentheses
                 * Adjust value of k: `k -= dp[a -1][b]`,
                 * Append a close bracket ')' 
                 * Decrease b
       Else k is invalid
  

  Notice that open bracket is less than close bracket in lexicographical order, so we always try to add open bracket first.