91Ó°ÊÓ

Let us assume that$s[1…n]$be original string that appear in any order

Let $f(i,j)=setofallpossiblevaluesofthesubstrings[i…j]for1≤i≤j≤n$

Here, i and j are starting and ending position of a string and length of string would be $(j-i).$

If a belongs to$f(i,j)$, then our algorithm will return true, else false.

Thus, if our output ‘a’ belongs to $f(1,n)$that means there we can parenthesize the string.

Let us assume a variable ‘j’ is use to find the position where the string $s[i……i+p]$is separated.

Now, because of ‘j’ we know about the split position of the string into two sub-result, and we can compute the result by taking union of the sub-results.

Thus we have,

localid="1657276451955" $\mathbf{f}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{i}\mathbf{+}\mathbf{k}\mathbf{)}\mathbf{=}\underset{\mathbf{i}\mathbf{≤}\mathbf{j}\mathbf{≤}\mathbf{i}\mathbf{+}\mathbf{k}}{\mathbf{∪}}\left\{mn:m∊f(i,j),n∊f(j+1,i+k)\right\}$

Now for$i=j$

There would be only one character in entire$s[1….n]$, which would be

Then$s\left[i\right]=x$

Else$FALSE$

Else localid="1657275948758" $FALSE$

Now if $i>j$, this means our substring $s[i….j]$comprises of more than one character.

In this case if $s[i….j]$can be split into two parts, then$f(i,j,x)=TRUE$.

We have matrix f() which will be storing value of ‘f’

Initiate$f(n,n,3)$

$$\begin{gathered} for(i=1ton) \\ for(j=1ton) \\ for(k∊a,b,c) \\ if(i==jANDp[i]==k) \\ f(i,j,k)=1 \\ else \\ f(i,j,k)=-1 \end{gathered}$$

function valid$(i,j,m)$

$if\left(f\right(i,j,m)≠-1)$

return $f(i,j,m)$

Now in this if our program return value of matrix $f(i,j,m)$, this means the string would be parenthesize, and resulting expression will return ‘a’.