Managing amortized time complexity in multi-step DPs.

This article will talk about the solution to the LeetCode problem 2911 — *Minimum Changes to Make K Semi-palindromes* as linked below.

Given a string *s* of length *n*, return the minimum number of letter changes required so that it can be partitioned into *k* semi-palindromic substrings. A string of length *m* is semi-palindromic iff (1) there exists some 1* ≤ d < m* such that *d* divides* m* and (2) characters at indices that have the same modulo by *d* form palindromes. Note that *d *must be less than *m*, meaning a palindrome is not necessarily semi-palindromic on its own.

The way that we will attack this is reminiscent of LeetCode 1147 that we talked about in an earlier article. Specifically, we will sequentially solve a couple of related dynamic programming problems and keep the time complexity of each in O(n³).

To answer the question, intuitively, we could define a sub-problem *dp(n, k)* as the minimum letter changes to make a prefix of length *n* able to be partitioned into *k *semi-palindromes. To solve such a sub-problem, we could reduce it to smaller sub-problems by enumerating the last substring of the partition in O(n) time, so all the sub-problems can be solved in O(k⋅n²) time. Let’s denote *p(n, i)* as the number of letter changes to make a substring of length *n* starting at index *i* become a semi-palindrome. Then the state transition is as follow.

Now we need to solve *p(n, i)*, which is another dynamic programming. Denote *q(d, m, j) *as the number of letter changes needed to make the subsequence *s[j], s[j+d], …, s[j+(m-1)*⋅*d]* palindromic. The state transition of *p* can be represented as follow.

A naive solution would lead to O(n²) time for each sub-problem by enumerating all *d < n*, making the total time complexity O(n⁴). However, using the idea from Vlad’s post, we could reduce the total time complexity to O(n³). As in the Sieve of Eratosthenes, where we enumerate divisors to update their multiples, we enumerate *d* and update the values of each *p(m*⋅d*, i)* instead of solving each *p(n, i) *one at a time. Note that despite the three dimensions of *q(d, m, j) *there are only O(n²) sub-problems due to the fact that *d ⋅ m ≤ n. *Each *q(d, m, j)* contributes to at most O(n) sub-problems for *p(n, i)* as part of some sliding window sum. So as long as we know *q(d, m, j)*, we’ll be able to derive *p(n, i)* in O(n³) time.

Now the problem comes down to *q(d, m, j)*. By leveraging the palindromic structure, we can easily get an O(1)-time state transition from one sub-problem to another.

In conclusion, the whole problem can be solved in O(n³) time by breaking it down into three dynamic programming problems. If you haven’t, I encourage you to try it at leetcode.com.