Replace the Substring for Balanced String

Medium
794.

Replace the Substring for Balanced String

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.

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'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var balancedString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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'.

Hints for Replace the Substring for Balanced String

  1. Hint 1

    Whatever the replaced substring becomes, you get to choose it freely — so only the characters outside it matter.

  2. Hint 2

    A window is replaceable exactly when every character outside it occurs at most n / 4 times.

  3. 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

  1. Tally the whole string. If every count is already at most n / 4, return 0.
  2. Extend the right edge, removing s[r] from the outside tally.
  3. While the outside tally is within quota, record the window length and pull the left edge in, putting s[l] back.
  4. 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

Java

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