22. Replace the Substring for Balanced String

You are given a string containing only 4 kinds of characters 'Q', 'W', 'E' and 'R'.

A string is said to be balanced if each of its characters appears n/4 times where n is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string s balanced.

Return 0 if the string is already balanced.

Example 1:

Input: s = "QWER"
Output: 0
Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER". 

Example 4:

Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

Solution: (Sliding Window)

Approach: Count number of each occurrences of each character. If any char occurs more then count the number of times it occurs more. Find the minimum windows substring to eliminate this additional count

class Solution
{
public:
    int balancedString(string s)
    {

        int n = s.length();
        int max = n / 4;
        int e = 0, w = 0, q = 0, r = 0;

        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == 'Q')
            {
                q++;
            }
            else if (s[i] == 'W')
            {
                w++;
            }
            else if (s[i] == 'E')
            {
                e++;
            }
            else
            {
                r++;
            }
        }

        int qc = max - q > 0 ? 0 : q - max;
        int qw = max - w > 0 ? 0 : w - max;
        int qe = max - e > 0 ? 0 : e - max;
        int qr = max - r > 0 ? 0 : r - max;

        if (qc + qw + qe + qr == 0)
        {
            return 0;
        }

        int i = 0;
        int start = 0;

        int cc = 0, cw = 0, ce = 0, cr = 0;
        int minLen = INT_MAX;

        while (i < s.length())
        {
            if (s[i] == 'Q')
            {
                cc++;
            }
            else if (s[i] == 'W')
            {
                cw++;
            }
            else if (s[i] == 'E')
            {
                ce++;
            }
            else
            {
                cr++;
            }

            while (start <= i && cc >= qc && cw >= qw && ce >= qe && cr >= qr)
            {
                if (s[start] == 'Q')
                {
                    cc--;
                }
                else if (s[start] == 'W')
                {
                    cw--;
                }
                else if (s[start] == 'E')
                {
                    ce--;
                }
                else
                {
                    cr--;
                }

                minLen = min(minLen, i - start);
                start++;
            }

            i++;
        }

        return minLen + 1;
    }
};

Time Complexity: O(n)