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.
