<p>You are given a string s of length <code>n</code> containing only four kinds of characters: <code>&#39;Q&#39;</code>, <code>&#39;W&#39;</code>, <code>&#39;E&#39;</code>, and <code>&#39;R&#39;</code>.</p>

<p>A string is said to be <strong>balanced</strong><em> </em>if each of its characters appears <code>n / 4</code> times where <code>n</code> is the length of the string.</p>

<p>Return <em>the minimum length of the substring that can be replaced with <strong>any</strong> other string of the same length to make </em><code>s</code><em> <strong>balanced</strong></em>. If s is already <strong>balanced</strong>, return <code>0</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;QWER&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> s is already balanced.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;QQWE&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We need to replace a &#39;Q&#39; to &#39;R&#39;, so that &quot;RQWE&quot; (or &quot;QRWE&quot;) is balanced.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;QQQW&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can replace the first &quot;QQ&quot; to &quot;ER&quot;. 
</pre>

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

<ul>
	<li><code>n == s.length</code></li>
	<li><code>4 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>n</code> is a multiple of <code>4</code>.</li>
	<li><code>s</code> contains only <code>&#39;Q&#39;</code>, <code>&#39;W&#39;</code>, <code>&#39;E&#39;</code>, and <code>&#39;R&#39;</code>.</li>
</ul>

class Solution:
    def balancedString(self, s: str) -> int:
        counter = Counter(s)
        toReplace = {}
        # print('counter ', counter)
        for k, v in counter.items():
            if v > len(s) // 4:
                toReplace[k] = v - len(s) // 4

        res = len(s)
        need = set(toReplace.keys())
        seen = dict()
        left = right = 0
        # print('toreplace', toReplace)
        if not need:
            return 0

        
        while left <= right < len(s):
            # print('\n left', left, '; right', right, '; seen', seen, '; need', need, '; res', res)
            if s[right] in toReplace:
                seen[s[right]] = seen.get(s[right], 0) + 1
                if s[right] in need and seen[s[right]] >= toReplace[s[right]]:
                    need.remove(s[right])
            # print('   seen', seen, '; need', need)
            
            
            right += 1
            while left <= right and not need:
                # print('  left', left, 'right', right, 'seen', seen)
                res = min(res, right - left)
                if s[left] in seen:
                    seen[s[left]] -= 1

                    if seen[s[left]] < toReplace[s[left]]:
                        need.add(s[left])

                left += 1       
                  
            
        return res
                    

        
116