#1234

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Replace the Substring for Balanced String

Determine the minimum substring length to replace in order to balance a string of Q, W, E, and R characters efficiently.

string sliding window

Problem Statement

Given a string s of length n containing only characters 'Q', 'W', 'E', and 'R', a string is considered balanced if each character occurs exactly n/4 times. You are tasked with finding the minimum length of a substring that can be replaced with any other string of the same length to achieve this balance.

Return 0 if the string is already balanced. Otherwise, determine the smallest possible substring length whose replacement will balance the string, ensuring that after replacement, each character appears exactly n/4 times.

Examples

Example 1

Input: s = "QWER"

Output: 0

s is already balanced.

Example 2

Input: s = "QQWE"

Output: 1

We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3

Input: s = "QQQW"

Output: 2

We can replace the first "QQ" to "ER".

Constraints

n == s.length
4 <= n <= 105
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.

Solution Approach

Track Excess Characters

Count the frequency of each character and identify those exceeding n/4. These are the only characters that need to be reduced by replacing a substring.

Apply Sliding Window

Use two pointers to define a window. Slide the window across the string while keeping track of character counts outside the window. When all outside counts are within n/4, record the window length as a candidate for minimum replacement.

Update and Minimize

Move the window to try smaller replacements, updating the character counts dynamically. Keep the smallest valid window length seen, which represents the minimum substring to replace.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed at most twice while sliding the window. Space complexity is O(1) due to the fixed-size character frequency map for 'Q', 'W', 'E', and 'R'.

What Interviewers Usually Probe

Candidate should recognize the need for a sliding window instead of brute-force substring checks.
Optimal solutions involve counting characters outside the window, not inside it, to simplify validation.
Tracking excess frequencies dynamically is a key optimization for linear-time performance.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the case when the string is already balanced, returning a non-zero length incorrectly.
Incorrectly updating counts when moving the window, leading to invalid balance checks.
Assuming replacement must be of specific characters instead of any string of the same length.

Follow-up variants

Determine maximum substring length that can be replaced without unbalancing the string.
Extend to strings with k distinct characters instead of exactly 4.
Find the minimum replacement substring when balancing requires exactly m occurrences per character instead of n/4.

FAQ

What is the best approach for Replace the Substring for Balanced String?

Use a sliding window with two pointers to track counts of characters outside the window, replacing the minimum substring to balance the string.

Why sliding window works for this problem?

Because only the counts outside the current window need to satisfy the n/4 constraint, allowing linear-time substring evaluation.

How do I handle a string that is already balanced?

Check initial frequencies of all characters; if each occurs exactly n/4 times, return 0 immediately.

Can this approach handle very large strings efficiently?

Yes, since it only processes each character at most twice and maintains a fixed-size frequency map, the method scales linearly.

What is the key optimization in Replace the Substring for Balanced String?

Maintaining a running state of character counts outside the window and shrinking the window dynamically to minimize substring length.

terminal

Solution

Solution 1: Counting + Two Pointers

First, we use a hash table or array `cnt` to count the number of each character in string $s$. If the count of all characters does not exceed $n/4$, then the string $s$ is balanced, and we directly return $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#1208 get equal substrings within budget #1297 maximum number of occurrences of a substring #1156 swap for longest repeated character substring