<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>


bool valid(map<char, int>* changemap, string* s, int start, int end)
        {
            bool pass = true;
            for (auto pair:*changemap)
            {
                if (count(s->begin()+start,s->begin()+end,pair.first) < pair.second)
                    pass = false;
            }
            if (pass)
                return true;

            return false;
        }

int search_j(map<char, int>* changemap, string* s, int i,int js, int je)
        {
        if (je-js ==1)
        {
            //cout <<"final split" << je << endl;

            return je;
        }
        int split  = js+((je-js)/2);
        //cout << js << "---" << je <<  "  split: " << split << endl;
        
        bool val =  valid( changemap, s, i,split);
        //cout << val << " Valid" << endl;
        if (val==true)
            return search_j( changemap, s, i, js,split);
        else
            return search_j( changemap, s, i, split,je);
        }



class Solution {
public:
    int balancedString(string s) {
        
    map<char, int> charcount;
    map<char, int> changemap;

    charcount['Q'] = 0;
    charcount['R'] = 0;
    charcount['W'] = 0;
    charcount['E'] = 0;

    for (char let:s)
    {
        charcount[let] ++;
    } 


    cout << s.size() << "size" << endl;

    int change_count = 0;
    for (auto pair:charcount)
    {
        //cout << pair.first << '-' << pair.second << endl;
        if (pair.second !=  s.size()/4)
        {
            int remcount = max(pair.second-(int(s.size()))/4,0 );
            if( remcount > 0)
            {
                changemap[pair.first] += remcount; 
                change_count += remcount ;

            }
        }
    }


    for (auto pair: charcount)
    {
        cout << string({pair.first}) << "-" << pair.second << endl ;
        if (pair.second == s.size())
        {
            return change_count;
        }
    } 

    if (change_count ==0)
    {
        return 0;
    }
    int min_wind = change_count;

    cout << min_wind << "min window" << endl;

    bool done = false;
    int i = 0;
    int j = 0 + min_wind;
    int max_wind = 999999999;
    while( j <= s.size()  && i <= s.size()-min_wind)
    {
        int width = j-i;
        bool val =  valid( &changemap, &s, i,j);
        cout << val << " --" << i << "----" <<j << endl;
        if (val)
        {
             max_wind = min(max_wind, width);
            i++;
        }
        else
            j++;
            //j= search_j( &changemap, &s, i,j,s.size()+1);

    }

    return max_wind;
    }
};
10300