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.length4 <= n <= 105n is a multiple of 4.s contains only 'Q', 'W', 'E', and 'R'.Problem Overview: You get a string containing only Q, W, E, and R. A string is balanced when each character appears exactly n/4 times. The task is to find the minimum length substring you can replace so the remaining string becomes balanced.
Approach 1: Sliding Window Approach (O(n) time, O(1) space)
This approach uses a frequency counter and a dynamic window to track which substring could be replaced. First count how many times each character appears. Any character exceeding n/4 is considered extra. Expand a right pointer to include characters in the window and decrease their counts from the outside frequency map. Once all remaining characters outside the window satisfy the balanced condition (count[c] ≤ n/4), shrink the window using the left pointer to minimize its length. Because each index moves at most once, the total time complexity is O(n) and the space complexity is O(1). This method relies on the classic sliding window pattern combined with frequency counting.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The two-pointer technique frames the same idea more explicitly: maintain left and right pointers that represent the candidate substring to replace. As right moves forward, update counts for characters leaving the "outside" portion of the string. When the outside portion becomes valid (no character exceeds n/4), move left forward to shrink the window while updating the minimum length. This method still scans the string only once and uses a constant-size frequency array because the alphabet is fixed. The approach is closely related to both two pointers and sliding window patterns used in many string optimization problems.
Recommended for interviews: Interviewers expect the Sliding Window solution. A brute force approach that tries all substrings would be O(n^2) and fails for large inputs. Demonstrating the window technique shows you understand how to maintain constraints dynamically while scanning the string in linear time.
The sliding window technique is ideal for problems involving substrings or adding elements to arrays incrementally. Here, we'll form a window which slides over the string until each possible character's frequency is less than or equal to n/4, starting from the beginning of the string and moving rightwards.
This function seeks the shortest substring such that replacing it makes other frequencies balanced. It uses character counting and string manipulation, applying a sliding window to reduce the space of search efficiently.
Time Complexity: O(n), as every index is visited at most twice.
Space Complexity: O(1), as the addition of auxiliary storage is constant.
This approach increases string traversal efficiency by using two pointers to monitor segment boundaries, overflowing initially until satisfied by frequency and effectively reducing substring lengths by adjusting inward.
The C code implements a two-pointer technique with an initial frequency count for excess characters, tuning explicitly within the string length constraints.
Time Complexity: O(n)
Space Complexity: O(1)
First, we use a hash table or array cnt to count the number of each character in string s. If the count of all characters does not exceed n/4, then the string s is balanced, and we directly return 0.
Otherwise, we use two pointers j and i to maintain the left and right boundaries of the window, initially j = 0.
Next, we traverse the string s from left to right. Each time we encounter a character, we decrease its count by 1, then we check whether the current window meets the condition, that is, the count of characters outside the window does not exceed n/4. If the condition is met, we update the answer, then move the left boundary of the window to the right until the condition is not met.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(C). Where n is the length of the string s; and C is the size of the character set, in this problem C = 4.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), as every index is visited at most twice. |
| Two-Pointer Technique | Time Complexity: O(n) |
| Counting + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Check | O(n^2) | O(1) | Conceptual understanding or very small inputs |
| Sliding Window with Frequency Count | O(n) | O(1) | Optimal solution for large strings and interview settings |
| Two-Pointer Technique | O(n) | O(1) | Alternative implementation of the same window idea with explicit pointers |
Replace the Substring for Balanced String | LeetCode 1234 | Coders Camp • Coders Camp • 6,706 views views
Watch 9 more video solutions →Practice Replace the Substring for Balanced String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor