Let's run the Floyd – Warshall algorithm on the matrix a_{ij} 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 \le i \le 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 \ge 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 a_{ij}, we construct the cost matrix cst. We also compute the matrix ps.
All values of dp[1][j]~(0 \le j \le 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" \to "aa") = cnt['a']['a'] + cnt['b']['a'] = 0 + 2 = 2;
dp[2][1] = ("ab" \to "bb") = cnt['a']['b'] + cnt['b']['b'] = 1 + 0 = 1;
dp[2][2] = ("ab" \to "cc") = cnt['a']['c'] + cnt['b']['c'] = 4 + 4 = 8;
dp[2][3] = ("ab" \to "dd") = cnt['a']['d'] + cnt['b']['d'] = 4 + 4 = 8;
dp[2][4] = ("ab" \to "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 \le j \le 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".
Comments