Move from brute-force thinking to an efficient approach using sliding window strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Sliding Window
"QWER"
"QQWE"
"QQQW"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
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;
}
}
// Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
func balancedString(s string) int {
cnt := [4]int{}
t := "QWER"
n := len(s)
for i := range s {
cnt[strings.IndexByte(t, s[i])]++
}
m := n / 4
if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m {
return 0
}
ans := n
for i, j := 0, 0; i < n; i++ {
cnt[strings.IndexByte(t, s[i])]--
for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m {
ans = min(ans, i-j+1)
cnt[strings.IndexByte(t, s[j])]++
j++
}
}
return ans
}
# Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
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 ans
// Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
struct Solution;
impl Solution {
fn balanced_string(s: String) -> i32 {
let mut count: Vec<usize> = vec![0; 256];
let s: Vec<u8> = s.bytes().collect();
let n = s.len();
let k = n / 4;
for i in 0..n {
count[s[i] as usize] += 1;
}
let mut start = 0;
let mut end = 0;
let mut res = n;
while end < n {
count[s[end] as usize] -= 1;
end += 1;
while start < n
&& count[b'Q' as usize] <= k
&& count[b'W' as usize] <= k
&& count[b'E' as usize] <= k
&& count[b'R' as usize] <= k
{
res = res.min(end - start);
count[s[start] as usize] += 1;
start += 1;
}
}
res as i32
}
}
#[test]
fn test() {
let s = "QWER".to_string();
let res = 0;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQWE".to_string();
let res = 1;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQQW".to_string();
let res = 2;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQQQ".to_string();
let res = 3;
assert_eq!(Solution::balanced_string(s), res);
}
// Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1234: Replace the Substring for Balanced String
// 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;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.