Replace the Substring for Balanced String
MedPrompt
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 <= 105nis a multiple of4.scontains only'Q','W','E', and'R'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through every possible substring and checks if replacing it could lead to a balanced string. A replacement is possible if the counts of characters outside the chosen substring do not exceed the target count k = n / 4. We are looking for the shortest such substring.
Algorithm
- Calculate the target count
k = n / 4. - Calculate the total frequency of each character ('Q', 'W', 'E', 'R') in the original string
s. - If the string is already balanced (all counts equal
k), return 0. - Initialize
minLengthton. - Use two nested loops to iterate through all possible start (
i) and end (j) indices of a substring. - For each substring
s[i...j], determine the character counts within this substring (windowCount). - Check if this substring is a valid candidate for replacement. This is true if for every character
c,totalCount[c] - windowCount[c] <= k. This condition ensures that the characters remaining outside the window can be part of a balanced string. - If the condition is met, update
minLength = min(minLength, j - i + 1). - After checking all substrings, return
minLength.
Walkthrough
The core idea is to test every single substring as a potential candidate for replacement. For a substring s[i...j] to be a valid choice, the part of the string that remains untouched, s[0...i-1] and s[j+1...n-1], must be 'fixable'. This means that for each character, its count in the untouched parts must not be more than the n/4 limit, since we can only add characters during the replacement, not remove them from the outside. We can optimize the counting process, but the fundamental O(N^2) complexity of checking every substring remains.
class Solution { public int balancedString(String s) { int n = s.length(); int k = n / 4; int[] totalCount = new int[128]; for (char c : s.toCharArray()) { totalCount[c]++; } // Check if already balanced if (totalCount['Q'] == k && totalCount['W'] == k && totalCount['E'] == k && totalCount['R'] == k) { return 0; } int minLen = n; // Iterate over all possible substrings s[i..j] for (int i = 0; i < n; i++) { int[] windowCount = new int[128]; for (int j = i; j < n; j++) { // Add current character to the window windowCount[s.charAt(j)]++; // Check if replacing this window can make the string balanced if (totalCount['Q'] - windowCount['Q'] <= k && totalCount['W'] - windowCount['W'] <= k && totalCount['E'] - windowCount['E'] <= k && totalCount['R'] - windowCount['R'] <= k) { minLen = Math.min(minLen, j - i + 1); } } } return minLen; }}Complexity
Time
O(N^2), where N is the length of the string. The two nested loops iterate through all `O(N^2)` possible substrings. The work inside the inner loop is constant time.
Space
O(1), as we only use a few arrays of constant size (e.g., 128 for ASCII characters) to store character counts.
Trade-offs
Pros
Conceptually straightforward and easier to implement than more optimized solutions.
Cons
This approach is too slow for the given constraints (n up to 10^5) and will result in a Time Limit Exceeded error on most platforms.
A more efficient approach rephrases the problem. Instead of checking what's outside a substring, we determine what needs to be inside it. For the string to become balanced, we must replace a substring that contains all the 'excess' characters. An excess character is one whose total count is greater than n/4. The problem then becomes finding the shortest substring that contains at least the required number of each excess character. This is a classic sliding window problem.
Algorithm
- Calculate the target count
k = n / 4. - Calculate the total frequency of each character in
s. - Determine the number of excess characters for each type. For a character
c,excess[c] = max(0, totalCount[c] - k). - If all
excesscounts are 0, the string is already balanced, so return 0. - Initialize two pointers,
left = 0andright = 0, to define a window. Also, initializeminLength = nand awindowCountmap/array. - Iterate
rightfrom0ton-1to expand the window to the right. - At each step, add
s[right]to the window and updatewindowCount. - Check if the current window is 'valid' by comparing
windowCountwithexcess. The window is valid ifwindowCount[c] >= excess[c]for all charactersc. - If the window is valid, it's a potential solution. Update
minLength = min(minLength, right - left + 1). Then, try to find a smaller valid window by shrinking it from the left: decrement the count ofs[left]and incrementleft. Repeat this as long as the window remains valid. - Continue expanding with
rightuntil the end of the string. - Return
minLength.
Walkthrough
This optimal solution hinges on a key insight: the characters we can change are within the replacement substring. The characters outside are fixed. Therefore, the counts of characters outside the substring must be at most k = n/4. This is equivalent to saying that the substring we replace must contain enough of each character to reduce its total count down to k. For example, if there are 7 'Q's and k=5, we have an excess of 2 'Q's. The substring we replace must contain at least 2 'Q's. We can find the minimum length of such a substring using the sliding window technique.
class Solution { public int balancedString(String s) { int n = s.length(); int k = n / 4; int[] count = new int[128]; for (char c : s.toCharArray()) { count[c]++; } // Check if the string is already balanced if (count['Q'] == k && count['W'] == k && count['E'] == k && count['R'] == k) { return 0; } // Determine excess characters that need to be in the window int[] excess = new int[128]; boolean needsReplacement = false; for (char c : "QWER".toCharArray()) { if (count[c] > k) { excess[c] = count[c] - k; needsReplacement = true; } } if (!needsReplacement) return 0; // Should be caught by first check, but for clarity int left = 0; int minLen = n; int[] windowCount = new int[128]; for (int right = 0; right < n; right++) { // Expand window windowCount[s.charAt(right)]++; // Shrink window while it's valid while (windowCount['Q'] >= excess['Q'] && windowCount['W'] >= excess['W'] && windowCount['E'] >= excess['E'] && windowCount['R'] >= excess['R']) { minLen = Math.min(minLen, right - left + 1); // Shrink from the left windowCount[s.charAt(left)]--; left++; } } return minLen; }}Complexity
Time
O(N), where N is the length of the string. The `right` pointer traverses the string once from left to right, and the `left` pointer does the same. Each character is processed a constant number of times.
Space
O(1), as the frequency maps/arrays used for counts have a constant size (for 4 characters, or 128 for all ASCII).
Trade-offs
Pros
Highly efficient with linear time complexity, making it suitable for large inputs.
Optimal space complexity.
Cons
The logic of transforming the problem and applying the sliding window can be less intuitive to come up with compared to the brute-force method.
Solutions
Solution
class Solution {public int balancedString(String s) { int[] cnt = new int[4]; String t = "QWER"; int n = s.length(); for (int i = 0; i < n; ++i) { cnt[t.indexOf(s.charAt(i))]++; } int m = n / 4; if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) { return 0; } int ans = n; for (int i = 0, j = 0; i < n; ++i) { cnt[t.indexOf(s.charAt(i))]--; while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) { ans = Math.min(ans, i - j + 1); cnt[t.indexOf(s.charAt(j++))]++; } } return ans; }}class Solution {public: int balancedString(string s) { int cnt[4]{}; string t = "QWER"; int n = s.size(); for (char &c : s) { cnt[t.find(c)]++; } int m = n / 4; if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) { return 0; } int ans = n; for (int i = 0, j = 0; i < n; ++i) { cnt[t.find(s[i])]--; while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) { ans = min(ans, i - j + 1); cnt[t.find(s[j++])]++; } } return ans; }};class Solution: def balancedString(self, s: str) -> int: cnt = Counter(s) n = len(s) if all(v <= n // 4 for v in cnt . values()): return 0 ans, j = n, 0 for i, c in enumerate(s): cnt[c] -= 1 while j <= i and all(v <= n // 4 for v in cnt . values()): ans = min(ans, i - j + 1) cnt[s[j]] += 1 j += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.