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.
