Skip to content

Replace the Substring for Balanced String⚓︎

Link

Description⚓︎

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

Constraints:

  • n == s.length
  • 4 <= n <= 10^5
  • n is a multiple of 4.
  • s contains only 'Q', 'W', 'E', and 'R'.

Solution⚓︎

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
private:
    // Helper method to check 
    // if the current window leads to a balanced string outside the window
    bool check(vector<int>& cnts, int len, int require) {
        /*
        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 string
        int totalAdjustments = 0;
        for (int i = 0; i < 4; i++) {
            // If any character's count outside the window is more than required
            if (cnts[i] > require) return false;
            // Add needed adjustments to achieve balance
            totalAdjustments += max(0, require - cnts[i]);
        }
        // Check if adjustments can be made within the current window length
        return totalAdjustments <= len;
    }

public:
    int balancedString(string s) {
        // Size of the input string
        int n = s.size();
        // Vector to map characters 'Q', 'W', 'E', 'R' to 0, 1, 2, 3
        vector<int> arr(n);
        // Vector to store counts of each character
        vector<int> cnts(4, 0);

        // Initialize character counts and mapping
        for (int i = 0; i < n; i++) {
            if (s[i] == 'Q') arr[i] = 0;
            else if (s[i] == 'W') arr[i] = 1;
            else if (s[i] == 'E') arr[i] = 2;
            else if (s[i] == 'R') arr[i] = 3;
            cnts[arr[i]]++;
        }

        // The required count of each character for the string to be balanced
        int require = n / 4;
        // Initialize the answer to the maximum possible value 
        // (length of the string)
        int res = n;

        // Use a sliding window approach to find the minimum length of substring to replace
        for (int left = 0, right = 0; left < n; left++) {
            // Expand the window to the right 
            // until the condition is met or the end of the string is reached
            while (right < n && !check(cnts, right - left, require)) {
                // Decrease the count of the character going into the window
                cnts[arr[right]]--;
                right++;
            }

            // If the condition is met, 
            // update the answer with the minimum window length
            if (check(cnts, right - left, require)) {
                res = min(res, right - left);
            }

            // Include the character at the current left of the window back into counts
            cnts[arr[left]]++;
        }

        return res;
    }
};

Way 2⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int balancedString(string s) {
        int n = s.size();
        vector<int> arr(n);
        vector<int> cnts(4, 0);
        for (int i = 0; i < n; i++) {
            switch (s[i]) {
                case 'Q': arr[i] = 0; break;
                case 'W': arr[i] = 1; break;
                case 'E': arr[i] = 2; break;
                default: arr[i] = 3; break;
            }
            cnts[arr[i]]++;
        }

        int require = n / 4;
        if (cnts[0] == require && cnts[1] == require 
        && cnts[2] == require && cnts[3] == require) {
            return 0;
        }

        int res = n, left = 0;
        for (int right = 0; right < n; right++) {
            cnts[arr[right]]--;
            while (cnts[0] <= require && cnts[1] <= require 
            && cnts[2] <= require && cnts[3] <= require) {
                res = min(res, right - left + 1);
                cnts[arr[left]]++;
                left++;
            }
        }
        return res;
    }
};

Sliding Window to Find Minimum Substring Length:

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: \(O(n)\), where \(n\) is the length of the input string. This reflects the efficient linear traversal of the input;
  • Space Complexity: \(O(n)\), mainly due to the additional array (arr) used for character mapping. The rest of the auxiliary space usage is constant.