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.
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; }}Video 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.