<p>You are given a string <code>s</code> and an integer <code>k</code>.</p>

<p>First, you are allowed to change <strong>at most</strong> <strong>one</strong> index in <code>s</code> to another lowercase English letter.</p>

<p>After that, do the following partitioning operation until <code>s</code> is <strong>empty</strong>:</p>

<ul>
	<li>Choose the <strong>longest</strong> <strong>prefix</strong> of <code>s</code> containing at most <code>k</code> <strong>distinct</strong> characters.</li>
	<li><strong>Delete</strong> the prefix from <code>s</code> and increase the number of partitions by one. The remaining characters (if any) in <code>s</code> maintain their initial order.</li>
</ul>

<p>Return an integer denoting the <strong>maximum</strong> number of resulting partitions after the operations by optimally choosing at most one index to change.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;accca&quot;, k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The optimal way is to change <code>s[2]</code> to something other than a and c, for example, b. then it becomes <code>&quot;acbca&quot;</code>.</p>

<p>Then we perform the operations:</p>

<ol>
	<li>The longest prefix containing at most 2 distinct characters is <code>&quot;ac&quot;</code>, we remove it and <code>s</code> becomes <code>&quot;bca&quot;</code>.</li>
	<li>Now The longest prefix containing at most 2 distinct characters is <code>&quot;bc&quot;</code>, so we remove it and <code>s</code> becomes <code>&quot;a&quot;</code>.</li>
	<li>Finally, we remove <code>&quot;a&quot;</code> and <code>s</code> becomes empty, so the procedure ends.</li>
</ol>

<p>Doing the operations, the string is divided into 3 partitions, so the answer is 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;aabaab&quot;, k = 3</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p>Initially&nbsp;<code>s</code>&nbsp;contains 2 distinct characters, so whichever character we change, it will contain at most 3 distinct characters, so the longest prefix with at most 3 distinct characters would always be all of it, therefore the answer is 1.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;xxyz&quot;, k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>The optimal way is to change&nbsp;<code>s[0]</code>&nbsp;or&nbsp;<code>s[1]</code>&nbsp;to something other than characters in&nbsp;<code>s</code>, for example, to change&nbsp;<code>s[0]</code>&nbsp;to&nbsp;<code>w</code>.</p>

<p>Then&nbsp;<code>s</code>&nbsp;becomes <code>&quot;wxyz&quot;</code>, which consists of 4 distinct characters, so as <code>k</code> is 1, it will divide into 4 partitions.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= k &lt;= 26</code></li>
</ul>

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        if k == 26 or k > len(set(s)):  return 1

        if k == 1:
            mx, cur, cnt, prev = 0, 0, -1, ''
            for c in s:
                if c == prev:
                    cur += 1
                else:
                    mx = max(mx, cur)
                    cur, prev = 1, c
                    cnt += 1
            mx = max(mx, cur)
            return cnt + min(mx, 3)
        
        n, s = len(s), [1 << ord(c)-97 for c in s]

        suff1, suff2, setMap, inds = [0]*n, [0]*n, [0]*n, {1<<i: n for i in range(26)}

        set1, cnt1, par1, ptr1 = 0, 0, 1, n-1
        set2, cnt2, par2, ptr2 = 0, 0, 1, n-1

        for i in range(n-1,-1,-1):

            suff2[i], setMap[i] = par2, set1

            if not set2 & s[i]:
                if cnt2 == k-1:
                    while ptr2 > inds[s[ptr2]]:    ptr2 -= 1
                    par2 = suff1[ptr2] + 1
                    set2 ^= s[ptr2]
                    ptr2 -= 1
                    cnt2 -= 1
                set2 |= s[i]
                cnt2 += 1

            if not set1 & s[i]:
                if cnt1 == k:
                    while ptr1 > inds[s[ptr1]]:    ptr1 -= 1
                    par1 = suff1[ptr1] + 1
                    set1 ^= s[ptr1]
                    ptr1 -= 1
                    cnt1 -= 1
                set1 |= s[i]
                cnt1 += 1
            
            suff1[i], inds[s[i]] = par1, i

        res = suff1[0]
        mode1, mode2 = False, False
        set0, cnt0, par0, mask = 0, 0, 1, (1<<26)-1

        for i in range(n):

            if not set0 & s[i]:

                if cnt0 == k-1:
                    if mode1:
                        res = max(res, par0 + suff1[i])
                    mode2 = True

                elif cnt0 == k:
                    mode1, mode2 = False, False
                    set0, cnt0 = 0, 0
                    par0 += 1

                set0 |= s[i]
                cnt0 += 1

            elif mode2:
                if set0 | setMap[i] < mask:
                    res = max(res, par0 + suff2[i])
                else:
                    res = max(res, par0 + suff1[i])
                mode2 = False

            elif not mode1:
                mode1 = True
            
        return res
48