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!