Question

A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position first has a better cost of 20+17=37.

Give a dynamic programming algorithm that, given the locations of m cuts in a string of length , finds the minimum cost of breaking the string into m +1 pieces.

Short answer

It is given in the question, that the primitive operation will take $0\left(n\right)$ time for copying the original string of length ‘n’. Hence, the cost of complete algorithm will be greater then $0\left(n\right)$.

To get minimum cost of breaking the string, we will use dynamic programming algorithm and define our recursion relation which will be our subproblem.

Step-by-step solution

Defining the Subproblem

Let us suppose that we have input string ‘S’ of length ‘n’. Then, also let ‘i’ denote the position of cut. Thus$i=1,2.....m$.

So, if m cuts are made, that means we havesubstrings.

So, let atmade the cut on our original string

So, we got two substrings: $S\left[1....i\right]$and$S\left[i+1...n\right]$ . But still$m-1$cut is to be made. Now, two cases will arise:

• If$m-1$remaining cut is made in substring$S\left[1....i\right]$
• If$m-1$remaining cut is made in substring$S\left[i+1...n\right]$

In any one of the above two case, there must be minimum cost.

Let $x_0,x_2,....x_{m+1}$be the position(index) where we have to make cut. Here, $x_1=0$and $x_m=n$.

Let $L\left(i,j\right)$denotes the minimum cost to cut the string, and $i=0...m$and $j=1....m+1$.

These strings will start from $x_i$and ends to $x_j$.

So our recursive equation will be:

$\mathbf{L}\left(i,j\right)\mathbf{=}\{\begin{array}{l}0;\mathrm{for}j=i+1\\ \left(x_j-x_i\right)+{\min }_{\mathit{i}\mathit{<}\mathit{k}\mathit{<}\mathit{j}}\left\{L\left(i,k\right),L\left(k+1,j\right)\right\};\mathrm{for}j>i+1\end{array}$

Analysing the recursive equation

The above recursive relation will run for $0\left(n^2\right)$And it is already mention in the question that we use primitive operation to store each string. And taking our string of length ‘$n$’, our effective time complexity will be$0\left(n^3\right)$.