Problem Description

You have a string s that contains only four types of characters: 'Q', 'W', 'E', and 'R'. The length of this string is n.

A string is considered balanced when each of the four characters appears exactly n/4 times in the string.

Your task is to find the minimum length of a substring that you can replace with any other characters to make the entire string balanced. You can replace the substring with any characters you want, as long as the replacement has the same length as the original substring.

If the string is already balanced, return 0.

For example:

• If s = "QWER" with length 4, it's already balanced since each character appears exactly 1 time (4/4 = 1), so return 0
• If s = "QQWE" with length 4, it's not balanced. You could replace one 'Q' to get a balanced string, so the minimum substring length to replace would be 1
• If s = "QQQWWWEEEERRRR" with length 14, it's not balanced since we need each character to appear 14/4 = 3.5 times (but since this must be an integer, we need each to appear 3 times when n=12)

The key insight is that you need to find the shortest contiguous substring that, when replaced appropriately, would result in each of the four characters appearing exactly n/4 times in the entire string.

Intuition

Let's think about what makes a string balanced - each character must appear exactly n/4 times. If we have too many of some characters and too few of others, we need to replace the excess characters with the missing ones.

The key insight is that we need to find a substring that contains all the "excess" characters. Once we replace this substring, we can put whatever characters we need to achieve balance.

For example, if we need each character to appear 3 times but we have Q: 5, W: 2, E: 3, R: 2, then Q has 2 excess occurrences. We need to find the shortest substring containing at least 2 Qs - we can then replace those with the missing W and R.

This naturally leads to a sliding window approach. We want to find the minimum window that, when removed (and replaced), leaves us with at most n/4 of each character in the remaining part of the string.

Think of it this way: instead of tracking what's inside the window to replace, we track what's outside the window. The characters outside the window are what will remain after we replace the window's content. For the string to be balanced after replacement, the count of each character outside the window must not exceed n/4.

We can use two pointers to maintain this window:

1. Expand the window by moving the right pointer, which removes characters from the "outside" count
2. When the outside satisfies our condition (all counts ≤ n/4), try to shrink the window from the left to find the minimum size
3. Keep track of the minimum valid window size found

This approach works because once we find a valid window (where the outside has ≤ n/4 of each character), we can always replace the window's content with the exact characters needed to achieve perfect balance.

Learn more about Sliding Window patterns.

Solution Approach

We implement the sliding window approach using two pointers to find the minimum substring that needs to be replaced.

Step 1: Initial Count and Early Exit

First, we count the frequency of each character using a Counter (hash table):

cnt = Counter(s)
n = len(s)

If all characters already appear at most n/4 times, the string is already balanced:

if all(v <= n // 4 for v in cnt.values()):
    return 0

Step 2: Sliding Window Setup

Initialize variables for the answer and left pointer:

ans, j = n, 0

• ans starts at n (worst case: replace the entire string)
• j is the left boundary of our window (starts at 0)

Step 3: Expand and Contract Window

Iterate through the string with the right pointer i:

for i, c in enumerate(s):
    cnt[c] -= 1  # Remove current character from "outside" count

When we include a character in our window (at position i), we decrease its count in cnt. Now cnt represents the frequency of characters outside our window.

Step 4: Try to Shrink Window

While the characters outside the window satisfy our condition (all counts ≤ n/4):

while j <= i and all(v <= n // 4 for v in cnt.values()):
    ans = min(ans, i - j + 1)  # Update minimum window size
    cnt[s[j]] += 1              # Add character back to "outside" count
    j += 1                      # Shrink window from left

This inner loop:

1. Checks if removing the window [j, i] leaves valid counts outside
2. Updates the minimum window size if valid
3. Moves the left boundary right to find an even smaller valid window
4. Adds the character at position j back to the outside count before moving j

Step 5: Return Result

The algorithm continues until we've considered all possible windows, then returns the minimum size found:

return ans

Time Complexity: O(n) where n is the length of the string. Although we have nested loops, each character is visited at most twice (once by each pointer).

Space Complexity: O(1) since we only track counts for at most 4 different characters.

Example Walkthrough

Let's walk through the solution with s = "QQQWWWEEEERRRR" (length 14).

Step 1: Initial Setup

• n = 14, so we need each character to appear n/4 = 14/4 = 3 times (integer division)
• Count frequencies: Q: 3, W: 3, E: 4, R: 4
• Since E and R both appear 4 times (more than 3), the string is not balanced

Step 2: Identify the Problem

• We have 1 excess E and 1 excess R
• We need to find the shortest substring containing at least 1 E and 1 R to replace

Step 3: Sliding Window Process

Initialize: ans = 14, j = 0, cnt = {Q: 3, W: 3, E: 4, R: 4}

Window [0, 9]: "QQQWWWEEEE"

• As we expand right pointer i from 0 to 9, we remove characters from outside count:
  • After including positions 0-2: cnt = {Q: 0, W: 3, E: 4, R: 4}
  • After including positions 3-5: cnt = {Q: 0, W: 0, E: 4, R: 4}
  • After including positions 6-9: cnt = {Q: 0, W: 0, E: 0, R: 4}
• Outside count invalid (R: 4 > 3), so we can't shrink yet

Window [0, 10]: "QQQWWWEEEЕР"

• Include position 10 ('R'): cnt = {Q: 0, W: 0, E: 0, R: 3}
• Now all counts ≤ 3! Valid window found
• Try shrinking from left:
  • Current window size: 11
  • Update ans = min(14, 11) = 11
  • Add s[0]='Q' back: cnt = {Q: 1, W: 0, E: 0, R: 3}
  • Move j to 1

Window [1, 10]: "QQWWWEEEЕР"

• Still valid (all counts ≤ 3)
• Window size: 10
• Update ans = min(11, 10) = 10
• Continue shrinking...

Continue this process, trying smaller windows like [7, 11]: "EEEЕР" (size 5)

• Outside this window: cnt = {Q: 3, W: 3, E: 0, R: 3}
• All counts ≤ 3, so valid!
• Update ans = min(previous, 5) = 5

Final Answer: 5

The shortest substring we need to replace is length 5 (e.g., "EEEЕР"). We can replace it with "QWEER" or any combination that balances the string.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. Although there's a nested loop structure with the outer for loop and inner while loop, each character in the string is visited at most twice - once by the pointer i (moving right) and once by the pointer j (moving left). The pointer j only moves forward and never resets, making this a two-pointer sliding window approach. The all() function inside the loops checks at most 4 values (for characters 'Q', 'W', 'E', 'R'), which is a constant operation O(1).

The space complexity is O(C), where C is the size of the character set. In this problem, C = 4 since we only deal with the characters 'Q', 'W', 'E', and 'R'. The Counter object cnt stores at most 4 key-value pairs, making the space requirement constant O(4) = O(1). However, following the reference answer's notation, we express it as O(C) to be more general about the character set size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding What the Counter Represents

Pitfall: A common mistake is misunderstanding what char_count represents after we start the sliding window. Initially, it counts all characters in the string, but once we start moving the window, it represents the count of characters outside the window (not inside).

Why this happens: When we do char_count[char] -= 1 at position right, we're conceptually "removing" that character from the outside count because it's now part of our replacement window.

Example of the confusion:

# WRONG interpretation:
# "char_count tracks what's inside the window"

# CORRECT interpretation:
# "char_count tracks what's outside the window (what remains after replacement)"

2. Incorrect Validation Check

Pitfall: Checking if the window itself is valid rather than checking if what's outside the window is valid.

Wrong approach:

# INCORRECT: Checking if window contents are balanced
window_count = Counter(s[left:right+1])
if all(count == target_count for count in window_count.values()):
    # This doesn't help us determine if replacing this window fixes the string

Correct approach:

# CORRECT: Check if remaining characters (outside window) don't exceed target
if all(count <= target_count for count in char_count.values()):
    # If true, we can replace the window to balance the string

3. Off-by-One Error in Window Size Calculation

Pitfall: Incorrectly calculating the window size as right - left instead of right - left + 1.

Wrong:

min_window_size = min(min_window_size, right - left)  # Missing the +1

Correct:

min_window_size = min(min_window_size, right - left + 1)  # Inclusive range

4. Forgetting to Handle Edge Cases

Pitfall: Not handling strings where n is not divisible by 4.

Issue: The problem assumes n is divisible by 4 (since we need each character to appear exactly n/4 times). If this isn't guaranteed, you need to add validation:

def balancedString(self, s: str) -> int:
    n = len(s)
    # Add validation if needed
    if n % 4 != 0:
        return -1  # Or handle according to problem requirements
  
    target_count = n // 4
    # ... rest of the code

5. Premature Window Shrinking

Pitfall: Moving the left pointer before checking if the current window is valid.

Wrong order:

while left <= right:
    left += 1  # Moving left first
    char_count[s[left-1]] += 1
    if all(count <= target_count for count in char_count.values()):
        min_window_size = min(min_window_size, right - left + 1)

Correct order:

while left <= right and all(count <= target_count for count in char_count.values()):
    min_window_size = min(min_window_size, right - left + 1)  # Update first
    char_count[s[left]] += 1  # Then move pointer
    left += 1

The correct order ensures we capture the minimum valid window before shrinking it further.