Let us define a multiplication operation on three symbols $\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{,}\mathbf{c}\mathbf{}$according to the following table; thus $\mathbf{}\mathbf{ab}\mathbf{}\mathbf{=}\mathbf{}\mathbf{b}\mathbf{,}\mathbf{ba}\mathbf{}\mathbf{=}\mathbf{}\mathbf{c}$, and so on. Notice that the multiplication operation defined by the table is neither associative nor commutative.

Find an efficient algorithm that examines a string of these symbols, say bbbbac, and decides whether or not it is possible to parenthesize the string in such a way that the value of the resulting expression is . For example, on input $\mathit{b}\mathit{b}\mathit{b}\mathit{b}\mathit{a}\mathit{c}$your algorithm should return yes because$\mathbf{\left(}\mathbf{\right(}\mathit{b}\mathbf{\left(}\mathit{b}\mathit{b}\mathbf{\right)}\mathbf{\left)}\mathbf{\right(}\mathit{b}\mathit{a}\mathbf{\left)}\mathbf{\right)}\mathit{c}\mathbf{}\mathbf{=}\mathbf{}\mathit{a}$.

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

Let $f(i,j)=setofallpossiblevaluesofthesubstrings[i\dots j]for1\le i\le j\le 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\dots \dots 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{\le }\mathbf{j}\mathbf{\le }\mathbf{i}\mathbf{+}\mathbf{k}}{\mathbf{\cup }}\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\dots .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\dots .j]$comprises of more than one character.

In this case if $s[i\dots .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)\ne -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’.