Let's run the Floyd – Warshall algorithm on the matrix aij to determine the shortest time required to replace each letter with any other letter.
Then construct a cost matrix cst, where cst[i][j] (1≤i≤n) represents the minimum number of days needed to change the letter s[i−1] into the letter j.
For convenience in further calculations, we build a matrix ps that contains the column-wise prefix sums of the cost matrix cst:
ps[i][j]=cst[i][1]+cst[i][2]+...+cst[i][j]
Let dp[i][j] denote the minimum number of days required to transform the first i letters of the string s into a string that satisfies Bessie’s new requirements, with the last k letters of the new string being the letter j.
We can write the dynamic equations as follows:
Suppose the first i−1 letters of s уhave already been transformed into a string whose last k letters are all j. Then we simply change the letter s[i−1] to j, which can be done in cst[i][j] days.
dp[i][j]=dp[i−1][j]+cst[i][j]
To ensure that the last k letters of the new string are all j, consider the values dp[i−k][0],dp[i−k][1],...,dp[i−k][m−1]. Choose the smallest among them — that is, we transform the first i−k letters of s into a string satisfying Bessie's new requirements (we don't care which letter the substring of length i−k ends with; we only care that it can be obtained in the minimum number of days). After that, we replace the last k letters of the original string s — namely s[i−k],s[i−k+1],...,,s[i−1] — with the letter j, which takes
cst[i−k+1][j]+cst[i−k+2][j]+...+cst[i][j]
days. This sum can be computed in constant time using the prefix sum array ps:
cst[i−k+1][j]+cst[i−k+2][j]+...+cst[i][j]=ps[i][j]−ps[i−k][j]
We maintain an auxiliary array mn, where
mn[i]=min(dp[i][0],dp[i][1],...,dp[i][m−1])
Thus, the dynamic programming equation for this case (i≥k) takes the following form:
dp[i][j]=ps[i][j]−ps[i−k][j]+mn[i−k]
It remains to choose the smaller of the two options for dp[i][j].
The answer to the problem is the value
mn[n]=min(dp[n][0],dp[n][1],...,dp[n][m−1])
We don't care which particular k letters the new word Bessie ends with.
Example
In this example, the optimal solution is as follows: replace a with b, then d with e, and after that replace both e's with c. The total cost of the changes is 1+4+0+0=5 days, and the resulting string will be bbccc.
Using the matrix aij, we construct the cost matrix cst. We also compute the matrix ps.
All values of dp[1][j] (0≤j≤4) will be equal to +∞, since the length of the stripe cannot be less than k=2. Accordingly, mn[1]=+∞.
Let us now consider the process of computing the values of dp[2][j] (0 ≤ j ≤ 4).
dp[2][0]=("ab"→"aa")=cnt['a']['a']+cnt['b']['a']=0+2=2;
dp[2][1]=("ab"→"bb")=cnt['a']['b']+cnt['b']['b']=1+0=1;
dp[2][2]=("ab"→"cc")=cnt['a']['c']+cnt['b']['c']=4+4=8;
dp[2][3]=("ab"→"dd")=cnt['a']['d']+cnt['b']['d']=4+4=8;
dp[2][4]=("ab"→"ee")=cnt['a']['e']+cnt['b']['e']=4+4=8;
mn[2]=min(dp[2][0],dp[2][1],dp[2][2],dp[2][3],dp[2][4])=1
When computing the values of dp[3][j] (0≤j≤4), the equation
dp[3][j]=ps[3][j]−ps[1][j]+mn[1]
will not be used, since mn[1]=+∞. Therefore, to obtain strips from the first three letters, one can only extend the strips of length two that have already been constructed:
dp[3][0]=dp[2][0]+cst['c']['a']=2+5=7 ("aaa");
dp[3][1]=dp[2][1]+cst['c']['b']=1+5=6 ("bbb");
dp[3][2]=dp[2][2]+cst['c']['c']=8+0=8 ("ccc");
dp[3][3]=dp[2][3]+cst['c']['d']=8+3=11 ("ddd");
dp[3][4]=dp[2][4]+cst['c']['e']=8+2=10 ("eee");
The value of dp[4][0] can be obtained in two ways:
or
The second case is more optimal — two letters 'a' are appended to a two-character string. The value mn[2]=1 is achieved for the string "bb", which means the optimal string is "bbaa".
