Given a string s and integer K. You start creating a substring from the start until there are at most K distinct characters. You must choose the largest such substring and delete it. Again, you do the same thing until the entire string is deleted.
Also, you can replace at most one character of the string with any other character of your choice.

You have to find the maximum number of such deletions you can achieve.

$$$s = "aaaa", K = 1 $$$
$$$ans = 3$$$
Explanation: Initially, we could only achieve 1 deletion, but if you make $$$s = abaa$$$, now we can have 3 deletions.

$$$s.size()<=10^4$$$
$$$1<=K<=26$$$
s contains only lowercase English letters.

Please help me understand how to achieve an optimal solution to this question. Thanks!

Given an 0-index-based array. You have to make the array non-increasing or non-decreasing. The operation you can use:

1. Choose an index $$$0\leq i<n$$$.
2. Make $$$array[i] = array[i]-1$$$ or $$$array[i] = array[i]+1$$$.

Find the minimum operations required to achieve the target.

• $$$Array.size()\leq1000$$$
  
• $$$0\leq Array[i] \leq1000$$$

Sample: $$$array = [3,2,4,5,0]$$$
$$$ans = 4$$$
final $$$array = [3,3,3,3,0]$$$

Please help me understand how to reach an optimal solution.