Replace the Substring for Balanced String — Solution
Replace the Substring for Balanced String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Replace the Substring for Balanced String is a medium coding problem on strings, two pointers and sliding window, asked in Amazon, Google and Myntra interviews.
- Difficulty: Medium
- Topics: Strings, Two Pointers, Sliding Window
- Asked at: Amazon, Google, Myntra
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
s has length n (a multiple of 4) and contains only 'Q', 'W', 'E' and 'R'. It is balanced when each of the four characters occurs exactly n / 4 times.
You may replace one contiguous substring with any string of the same length. Return the minimum length of substring that must be replaced to make s balanced.
Example 1
Input: s = "QWER"
Output: 0
Explanation: Already balanced.
Example 2
Input: s = "QQWE"
Output: 1
Explanation: Replacing one Q with an R gives "RQWE".
Example 3
Input: s = "QQQW"
Output: 2
Explanation: Replace "QQ" with "ER".
Constraints
n == s.length4 <= n <= 100000n is a multiple of 4.s contains only 'Q', 'W', 'E' and 'R'.
Hints for Replace the Substring for Balanced String
Hint 1
Whatever the replaced substring becomes, you get to choose it freely — so only the characters outside it matter.
Hint 2
A window is replaceable exactly when every character outside it occurs at most
n / 4times.Hint 3
Find the shortest such window.
How to solve Replace the Substring for Balanced String
Invert the question: instead of asking what the replacement should be, ask when a window can be fixed. Since the replacement is arbitrary, a window works precisely when no character outside it already exceeds its quota — and that predicate improves as the window grows, so a shrinking sliding window finds the shortest one.
Approach
- Tally the whole string. If every count is already at most
n / 4, return 0. - Extend the right edge, removing
s[r]from the outside tally. - While the outside tally is within quota, record the window length and pull the left edge in, putting
s[l]back. - Return the shortest window recorded.
Why it works
The characters inside the window can be rewritten to exactly fill the remaining quota — the counts always add up because n is a multiple of 4 — so feasibility depends only on the outside. Growing the window removes characters from the outside, which never breaks feasibility, so the predicate is monotone and the two-pointer scan is valid.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Checking the counts inside the window instead of outside inverts the condition.
- The already-balanced case must return 0 before the loop, or the shrink never records anything.
- The window can be the whole string, so seed the best at
n.
Reference solution
Python
def balancedString(s: str) -> int:
n = len(s)
need = n // 4
cnt = {"Q": 0, "W": 0, "E": 0, "R": 0}
for ch in s:
cnt[ch] += 1
def ok() -> bool:
return all(v <= need for v in cnt.values())
if ok():
return 0
best = n
l = 0
for r in range(n):
cnt[s[r]] -= 1
while l <= r and ok():
best = min(best, r - l + 1)
cnt[s[l]] += 1
l += 1
return bestJava
public static int balancedString(String s) {
int n = s.length(), need = n / 4;
int[] cnt = new int[128];
for (int i = 0; i < n; i++) cnt[s.charAt(i)]++;
if (cnt['Q'] <= need && cnt['W'] <= need && cnt['E'] <= need && cnt['R'] <= need) return 0;
int best = n, l = 0;
for (int r = 0; r < n; r++) {
cnt[s.charAt(r)]--;
while (l <= r && cnt['Q'] <= need && cnt['W'] <= need && cnt['E'] <= need && cnt['R'] <= need) {
best = Math.min(best, r - l + 1);
cnt[s.charAt(l)]++;
l++;
}
}
return best;
}C++
int balancedString(string s) {
int n = (int) s.size(), need = n / 4;
vector<int> cnt(128, 0);
for (int i = 0; i < n; i++) cnt[(int) s[i]]++;
if (cnt['Q'] <= need && cnt['W'] <= need && cnt['E'] <= need && cnt['R'] <= need) return 0;
int best = n, l = 0;
for (int r = 0; r < n; r++) {
cnt[(int) s[r]]--;
while (l <= r && cnt['Q'] <= need && cnt['W'] <= need && cnt['E'] <= need && cnt['R'] <= need) {
best = min(best, r - l + 1);
cnt[(int) s[l]]++;
l++;
}
}
return best;
}JavaScript
var balancedString = function(s) {
var n = s.length;
var need = n / 4;
var cnt = { Q: 0, W: 0, E: 0, R: 0 };
for (var i = 0; i < n; i++) cnt[s.charAt(i)]++;
var ok = function() {
return cnt.Q <= need && cnt.W <= need && cnt.E <= need && cnt.R <= need;
};
if (ok()) return 0;
var best = n, l = 0;
for (var r = 0; r < n; r++) {
cnt[s.charAt(r)]--;
while (l <= r && ok()) {
if (r - l + 1 < best) best = r - l + 1;
cnt[s.charAt(l)]++;
l++;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique