5
$\begingroup$

Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is correctly parenthesized.

For example, for $s = ((????)))?$ the strings $((()(())))$ and $(()((())))$ are possible, so $f(s) \ge 2$.

GOAL. The task is to evaluate $f(s)$ efficiently, i.e. in subquadratic time in the length $n$ of $s$.

APPROACHES. I present my approaches as following. First, we can check in time $\mathcal{O}(n)$ if a string is correctly parenthesized and we always have $f(s) \le 2^n$. Thus, a $\mathcal{O}(n2^n)$ brute-force solution can be deduced. It's also quite an easy exercise to find one correct parenthesization of a string in time $\mathcal{O}(n)$, but that's not what I want. The goal is to count them.

Using dynamic programming the problem may be solved in time $\mathcal{O}(n^2)$. We define the potential $\varphi(s')$ of a string $s'$ as number of opening brackets "$($" minus number of closing brackets "$)$". For instance, we have $\varphi("((()()()") = 5 - 3 = 2$.

Denote by $dp(k, l)$ the number of ways to replace $?$ with $($ or $)$ in the substring $s_1s_2\dots s_k$ of $s = s_1s_2\dots s_n$ such that $\varphi(s') = l$ for the resulting string $s'$. We get the following reccurence:

$\displaystyle dp(k, l) = \begin{cases} dp(k - 1, l - 1) & \text{ for } s_k =\text{ }(, \\ dp(k - 1, l + 1) & \text{ for } s_k =\text{ }), \\ dp(k - 1, l - 1) + dp(k - 1, l + 1) & \text{ for } s_k =\text{ }?. \end{cases}$

The answer to original problem is $f(s) = dp(n, 0)$. Since there are $n \cdot \varphi_{max} \le n^2$ states (negative potentials are not allowed) and each state can be computed in time $\mathcal{O}(1)$, the total time complexity is $\mathcal{O}(n^2)$. Note that we assume addition to be a constant-time operation.

Are there any faster algorithms? Does this problem have a name and are there resources for further reading? I appreciate answers and thoughts to this problem.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you need the exact count, or are you willing to accept an approximate count? $\endgroup$ – D.W.♦ Oct 4 '17 at 0:41
  • $\begingroup$ If it is significantly faster than DP solution and the error is reasonable, a approximate count is also appreciated. $\endgroup$ – neutron-byte Oct 4 '17 at 10:44
  • $\begingroup$ Conjecture: given $s \in \Sigma^*$, we can find $\ell_1,\dots,\ell_n,u_1,\dots,u_n$ such that (1) almost all ways to complete $s$ to a fully parenthesized string $t \in \{(,)\}^*$ are good, and (2) $u_i-\ell_i \le 100\sqrt{n}$ for all $i$. Here we call a string $t$ good if $\ell_i \le \varphi(t_1 \cdots t_i) \le u_i$ for all $i$. (Why do I think this might be true? Based on an analogy with random walks.) You can compute the number of good strings in $O(n^{1.5})$ time using your DP algorithm. So if the conjecture is true, then you can approximate the answer. $\endgroup$ – D.W.♦ Oct 4 '17 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.