Yes, https://ideone.com/61Va4F

Yes, that's the intended solution. Also instead of using a dynamic convex hull for reversing the max/min, its easier to process the DP backwards, interchanging what represents m and c in y = mx + c. Dynamic CHT is kinda an unnecessary thing to do here.

As for other approaches. I have found someone using divide and conquer optimization too. Here is the solution.

EDIT: The intended solution: https://ideone.com/pWkx7f

They have been moved. :)

Hi, so to me seems like a notorious coincidence.

First of all, let's calculate for each i the rightmost index j such that in subarray [i....j] there are atmost k distinct values. Let's call it maxi[i]. I did this by maintaining count of elements in current range (use unordered map) and deque.

Now let dp[i] denote the answer if the original string was s[i...n]. Clearly answer is dp[1]. While updating dp[i], you can make partition of current substring at i, i + 1.....maxi[i]. Let's say you make partition at j then you have to add dp[j + 1] to dp[i]. So, we have to add the summation dp[j], j ranging from i + 1 to maxi[i] + 1. This can be done using fennwick/ segment tree.