<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 {
public:
    int balancedString(string s) {
        int n=s.size();
        vector<vector<int>>v(4,vector<int>(n,0));
        for(int i=0;i<n;i++){
            if(i){
                v[0][i]=v[0][i-1];v[1][i]=v[1][i-1];v[2][i]=v[2][i-1];v[3][i]=v[3][i-1];
                if(s[i]=='Q') v[0][i]=v[0][i-1]+1;
                if(s[i]=='W') v[1][i]=v[1][i-1]+1;
                if(s[i]=='E') v[2][i]=v[2][i-1]+1;
                if(s[i]=='R') v[3][i]=v[3][i-1]+1;
            }
            else{
                if(s[i]=='Q') v[0][i]=1;
                if(s[i]=='W') v[1][i]=1;
                if(s[i]=='E') v[2][i]=1;
                if(s[i]=='R') v[3][i]=1;
            }
        }
        cout<<v[0][n-1]<<" "<<v[1][n-1]<<" "<<v[2][n-1]<<" "<<v[3][n-1]<<endl;
        if(v[0][n-1]==n/4 && v[1][n-1]==n/4 && v[2][n-1]==n/4 && v[3][n-1]==n/4) return 0;
        int res=0;
        for(int j=0;j<4;j++){
            if(v[j][n-1]>n/4){
                auto idx=lower_bound(v[j].begin(),v[j].end(),(v[j][n-1]-n/4))-v[j].begin();
                res=max(res,(int)idx+1);
            }
        }
        cout<<res<<endl;
        for(int i=0;i<n;i++){
            int ans=0;
            if(v[0][i]>n/4 || v[1][i]>n/4 || v[2][i]>n/4 || v[3][i]>n/4) break;
            for(int j=0;j<4;j++){
            if(v[j][i]<=n/4){
            auto idx=lower_bound(v[j].begin(),v[j].end(),v[j][i]+(v[j][n-1]-n/4))-v[j].begin();
            cout<<idx<<" "<<i<<endl;
            if(idx!=n && idx>i) ans=max(ans,(int)idx-i);
            }
            }
            if(ans!=0) res=min(res,ans);
        }
        return res;
    }
};


15000