<p>You are given a string <code>s</code> and an integer <code>k</code>. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most <code>k</code> times.</p>

<p>Return <em>the length of the longest substring containing the same letter you can get after performing the above operations</em>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;ABAB&quot;, k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> Replace the two &#39;A&#39;s with two &#39;B&#39;s or vice versa.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;AABABBA&quot;, k = 1
<strong>Output:</strong> 4
<strong>Explanation:</strong> Replace the one &#39;A&#39; in the middle with &#39;B&#39; and form &quot;AABBBBA&quot;.
The substring &quot;BBBB&quot; has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only uppercase English letters.</li>
	<li><code>0 &lt;= k &lt;= s.length</code></li>
</ul>

class Solution:
    # Time: O(n)
    # Space: O(1)
    def getMajority(self, inSubstring):
        maxVal = 0
        optChar = ""
        for c in inSubstring:
            if inSubstring[c] > maxVal:
                maxVal = inSubstring[c]
                optChar = c
        return optChar
    
    # Time: O(n^2) (O(n) * O(n) for getMajority func)
    # Space: O(n)
    def characterReplacement(self, s: str, k: int) -> int:
        # for each index, tell the majority character in the string
        maxLen = 1
        L = 0
        inSubstring = defaultdict(int)
        inSubstring[s[0]] = 1
        maj = s[0]

        for R in range(1, len(s)):
            curr = s[R]
            inSubstring[curr] += 1
            if curr == maj:
                maxLen = max(maxLen, R - L + 1)
                continue
            else:
                maj = self.getMajority(inSubstring)
                while R - L + 1 - inSubstring[maj] > k:
                    toRemove = s[L]
                    L += 1
                    # actually remove
                    inSubstring[toRemove] -= 1
                    maj = self.getMajority(inSubstring)

                maxLen = max(maxLen, R - L + 1)
        return maxLen
            
            
"""
        AABBBBBB k=2 A:1 majority: A
        if curr is majority char, continue
        else if curr just became the majority char, recalculate how many ks need to be used
        if we have enough, continue
        else if curr just became the majority char and we don't have enough ks, keep doing L++ until we do
        else if curr did not become the majority char, calculate how many ks need to be used; if not enough,
        do L++ until we do
"""
16300