{x}
blog image

Replace the Substring for Balanced String

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

Solution Explanation for Replace the Substring for Balanced String

This problem asks us to find the minimum length of a substring that needs to be replaced to make the entire string balanced. A balanced string is defined as a string where each of the four characters ('Q', 'W', 'E', 'R') appears an equal number of times (n/4, where n is the string length).

Approach: Sliding Window

The most efficient approach uses a sliding window technique combined with character counting. Here's a breakdown:

  1. Character Counting: We first count the occurrences of each character in the input string s. We use a dictionary or array for efficient counting.

  2. Check for Balance: If the count of each character is already equal to n/4, the string is balanced, and we return 0.

  3. Sliding Window: We initialize a sliding window with the left pointer (j) at the beginning of the string and the right pointer (i). The window initially encompasses the entire string.

  4. Window Adjustment: We iterate through the string using i. For each character we encounter:

    • We decrement its count in our character counter.
    • We check if the current window satisfies the balance condition (i.e., the count of each character within the window is less than or equal to n/4).
    • If the balance condition is met:
      • We update the minimum window length (ans) found so far.
      • We move the left pointer (j) to the right, incrementing the counts of characters that are leaving the window until the balance condition is no longer met (this ensures that the shortest valid window is found)

  5. Return Minimum Length: Finally, we return the minimum window length (ans).

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. We iterate through the string once using a sliding window. The operations within the inner while loop execute at most O(n) times in total, because j can move only up to n.

  • Space Complexity: O(1). We use a fixed-size array (or dictionary) to store character counts, regardless of the input string's length. The space used is constant.

Code Implementation (Python)

from collections import Counter
 
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

The code in other languages (Java, C++, Go) follows the same algorithm; only the syntax and data structures differ slightly. The core logic remains the same—sliding window and character counting to find the minimum substring length for balance.