Google codejam APAC Test practice round: Parenthes

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

Let S= any valid sequence of parentheses from n( and n) . Now any valid sequence S can be written as S=X+Y where

• X=valid prefix i.e. if traversing X from left to right , at any point of time, numberof'(' >= numberof')'
• Y=valid suffix i.e. if traversing Y from right to left, at any point of time, numberof'(' <= numberof')'

For any S many pairs of X and Y are possible.

For our example: ()(())

`()(())` =`empty_string + ()(())` 
         = `( + )(())`
         = `() + (())` 
         = `()( + ())` 
         = `()(( + ))` 
         = `()(() + )`
         = `()(()) + empty_string`

Note that when X=empty_string, then number of valid S from n( and n)= number of valid suffix Y from n( and n)

Now, Algorithm goes like this: We will start with X= empty_string and recursively grow X until X=S. At any point of time we have two options to grow X, either append '(' or append ')'

Let dp[a][b]= number of valid suffixes using a '(' and b ')' given X

nop=num_open_parenthesis_left ncp=num_closed_parenthesis_left

`calculate(nop,ncp)
{
  if dp[nop][ncp] is not known
  {
    i1=calculate(nop-1,ncp); // Case 1: X= X + "("
    i2=((nop<ncp)?calculate(nop,ncp-1):0);
/*Case 2: X=X+ ")" if nop>=ncp, then after exhausting 1 ')' nop>ncp, therefore there can be no valid suffix*/
    dp[nop][ncp]=i1+i2;
  }
   return dp[nop][ncp];
}`

Lets take example,n=3 i.e. 3 ( and 3 ) Now at the very start X=empty_string, therefore

dp[3][3]= number of valid sequence S using 3( and 3 ) = number of valid suffixes Y from 3 ( and 3 )

Answer 2

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.