You are given a string s of length n containing only four 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 s balanced. If s is already balanced, return 0.
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".
classSolution{private:// Helper method to check // if the current window leads to a balanced string outside the windowboolcheck(vector<int>&cnts,intlen,intrequire){/* cnts: A vector of integers representing the counts of each character ('Q', 'W', 'E', 'R') outside the current sliding window. len: The length of the current sliding window. This is essentially the number of characters that can be replaced to try and balance the string. require: The required count of each character for the string to be balanced. */// Track total adjustments needed to balance the stringinttotalAdjustments=0;for(inti=0;i<4;i++){// If any character's count outside the window is more than requiredif(cnts[i]>require)returnfalse;// Add needed adjustments to achieve balancetotalAdjustments+=max(0,require-cnts[i]);}// Check if adjustments can be made within the current window lengthreturntotalAdjustments<=len;}public:intbalancedString(strings){// Size of the input stringintn=s.size();// Vector to map characters 'Q', 'W', 'E', 'R' to 0, 1, 2, 3vector<int>arr(n);// Vector to store counts of each charactervector<int>cnts(4,0);// Initialize character counts and mappingfor(inti=0;i<n;i++){if(s[i]=='Q')arr[i]=0;elseif(s[i]=='W')arr[i]=1;elseif(s[i]=='E')arr[i]=2;elseif(s[i]=='R')arr[i]=3;cnts[arr[i]]++;}// The required count of each character for the string to be balancedintrequire=n/4;// Initialize the answer to the maximum possible value // (length of the string)intres=n;// Use a sliding window approach to find the minimum length of substring to replacefor(intleft=0,right=0;left<n;left++){// Expand the window to the right // until the condition is met or the end of the string is reachedwhile(right<n&&!check(cnts,right-left,require)){// Decrease the count of the character going into the windowcnts[arr[right]]--;right++;}// If the condition is met, // update the answer with the minimum window lengthif(check(cnts,right-left,require)){res=min(res,right-left);}// Include the character at the current left of the window back into countscnts[arr[left]]++;}returnres;}};
The core of this solution lies in the sliding window approach, where two pointers (left and right) are used to dynamically adjust the window size and find the smallest possible substring that can be replaced to balance the string. The right pointer expands the window by moving to the right, and for each new position of right, the character count is decremented (cnts[arr[right]]--), effectively removing that character from consideration (assuming it could be part of the replaced substring).
Inside the loop, there's a nested while loop that checks if the string, excluding the current window, is balanced (i.e., the count of each character is less than or equal to require). If the condition is true, it tries to shrink the window from the left (by incrementing left and adjusting counts accordingly) while maintaining the balance condition. During this process, it updates res, the result variable, to hold the minimum length of the substring found that can be replaced to achieve balance.
By incrementing left inside the while loop only when the string excluding the current window is balanced, it ensures that the window size is as small as possible. The res variable is updated with the minimum window size found during this process (right - left + 1).
Complexity:
Time Complexity: , where is the length of the input string. This reflects the efficient linear traversal of the input;
Space Complexity: , mainly due to the additional array (arr) used for character mapping. The rest of the auxiliary space usage is constant.