Replace the Substring for Balanced String — Medium Problem & Solution

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.

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.length
4 <= n <= 100000
n is a multiple of 4.
s contains only 'Q', 'W', 'E' and 'R'.

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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue