Minimum number of charactor need to add to make a valid barrack string

Revision en14, by SPyofgame, 2021-02-05 13:56:41

### The full statement

Main statement

A pair of charactor $(L, R)$ is called good or matched to each other if it satisfy one of below

• $L =$ '(' and $R =$ ')'
• $L =$ '[' and $R =$ ']'
• $L =$ '{' and $R =$ '}'

Notice that if $(L, R)$ is good then $(R, L)$ is not good

String can have many variation of categories, one of that is good string. Let a string $S$ of size $N$ is called good if

• $S$ is empty (its length $N = 0$)
• $S = S_1 + S_2 + \dots + S_n$. Where $S_i$ is a good string and + symbol mean that string concaternation
• $S = L + S_x + R$ where $S_x$ is a good string and $(L, R)$ is a good pair of charactor

Given a string $S$ of size $N$. We can add some charactor '(', ')', '[', ']', '{', '}' into anywhere in string $S$ but you cant replace or remove them.

The question is that: What is the minimum number of charactor need to add into string to make it good ?

Limitation: $N = |S| \leq 500$

### The dynamic programming solution $O(n^3)$

Lets $F(l, r)$ is the answer for substring $S[l..r]$.

• If $l > r$ then the string is empty, hence the answer is $F(l, r) = 0$
• If $l = r$ then we should add one charactor to match $S_l$ to make this substring good, hence the answer is $F(l, r) = 1$
• We can split into 2 other substring $S[l..r] = S[l..k] + S[k+1..r]$, for each $k$ we have $F(l, r) = F(l, k) + F(k+1, r)$ hence $F(l, r) = min(F(l, k) + F(k+1, r))$
• Notice that when $S_l$ match $S_r$, $F(l, r) = min(F(l + 1, r - 1), min(F(l, k) + F(k+1, r)))$

Complexity:

• $F(l, r)$ have $O(n^2)$ states
• In each substring $S[l..r]$, we maybe to have a for-loop $O(n)$
• Hence the upper bound of the complexity is $O(n^3)$
Recursive Code
Iterative Code
Full Code

### The other dynamic programming solution $O(n^3)$

Base cases:

• If $l > r$ then the string is empty, hence $F(l, r) = 0$
• If $l = r$ then we should add one charactor to match $S_l$ to make this substring good, hence $F(l, r) = 1$

Branch and bound cases:

• If $S_l$ is close barrack, then add a open barrack before it, hence $F(l, r) = F(l + 1, r) + 1$
• If $S_r$ is open barrack, then add a close barrack after it, hence $F(l, r) = F(l, r - 1) + 1$
• If $(S_l, S_{l+1})$ is good, then just paired it up, hence $F(l, r) = F(l + 2, r) + 0$
• If $(S_{r-1}, S_r)$ is good, then just paired it up, hence $F(l, r) = F(l, r - 2) + 0$

Main cases:

For each $k = l \rightarrow r - 1$

• If $S_k$ match $S_r$, minimize $F(l, r)$ with $F(l, k - 1) + 0 + F(k + 1, r - 1)$
• Else add a open charactor at k to match $S_r$, minimize $F(l, r)$ with $F(l, k) + 1 + F(k + 1, r - 1)$

Complexity:

• $F(l, r)$ have $O(n^2)$ states
• In each substring $S[l..r]$, we maybe to have a for-loop $O(n)$ or $O(1)$ for transistion
• Hence the upper bound complexity is $O(n^3)$
• Hence the lower bound complexity is $O(n^2)$
Recursive Code
Full code
Optimize version

### My question

• If the string $S$ is only consist of '(' and ')' then there is a Linear ($O(n)$) solution
The solution
• Can my algorithm ($dp[l][r] = min(dp[l][k] + dp[k + 1][r])$) improved into $O(n^2\ polylog)$ or lower in somehow ?

• Failed to use Knuth algorithm $(dp[l][r] = min(dp[l][k] + dp[k][r] + cost[l][r])$ since fully-motone condition is not satisfied

#### History

Revisions

Rev. Lang. By When Δ Comment
en14 SPyofgame 2021-02-05 13:56:41 7556
en13 SPyofgame 2021-02-04 10:55:27 273
en12 SPyofgame 2021-02-04 10:53:42 256
en11 SPyofgame 2021-02-04 10:02:38 5508
en10 SPyofgame 2021-02-04 09:43:38 97
en9 SPyofgame 2021-02-04 08:02:15 303
en8 SPyofgame 2021-02-04 07:39:33 58
en7 SPyofgame 2021-02-04 07:18:50 2
en6 SPyofgame 2021-02-04 07:18:24 183
en5 SPyofgame 2021-02-04 07:13:19 192
en4 SPyofgame 2021-02-04 06:10:26 1008
en3 SPyofgame 2021-02-04 05:56:52 3217
en2 SPyofgame 2021-02-04 05:10:01 76
en1 SPyofgame 2021-02-04 05:08:52 3831 Initial revision (published)