1234. Replace the Substring for Balanced String Medium

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

Example 4:
Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

Approach

Input: A string s made only of QWER, capable of turning into a balanced string by replacing any continuous substring with whatever characters required.

Output: Return the minimum possible size of the substring to replace.

This issue relies on the Variable-length Sliding Window technique.

We can solve this recursively by determining the minimal window range enclosing the excess variables. Any values masked within replacing window bounds are malleable. The unmasked components outside the bound inherently must exhibit a frequency property satisfying balance independently.

More clearly, the target is localizing the minimum contiguous snippet [l, r], satisfying circumstances that: variables out of these bounds (i.e. s[:l] + s[r+1:]) each respectively number <= n // 4.

Why <= n // 4 specifically? Due to conditions where window interval >= sum of all completely surplus factors.

Implementation

python

class Solution:
    def balancedString(self, s: str) -> int:
        n = len(s)
        expected = n // 4  # Standard counts representing balanced string

        # Frequency mapping chart config
        freq = {'Q': 0, 'W': 0, 'E': 0, 'R': 0}

        # Tabulate full global footprint of QWER combinations
        for ch in s:
            freq[ch] += 1

        # Escapable directly if natural equilibrium is achieved outright without swapping
        if all(freq[c] == expected for c in "QWER"):
            return 0
        
        ans = n  # Init base span of the substring matching max length
        left = 0  # Sliding Window trailing anchor

        # Window boundary traverses string map up till limits
        for right in range(len(s)):
            freq[s[right]] -= 1  # Deduct representations, symbolically putting to "swapped" territory

            # Under assumptions remaining unmasked out of bound letter elements do not breach `expected`, leftover string chunks conform functionally
            while left < n and all(freq[c] <= expected for c in "QWER"):
                # Mark minimum window interval limits
                ans = min(ans, right - left + 1)

                # Move left pin traversing (effectively reinstating previous out-of-bounds representations)
                freq[s[left]] += 1
                left += 1
        
        return ans  # Return shortest viable swapping frame

javascript

/**
 * @param {string} s
 * @return {number}
 */
var balancedString = function(s) {
    // Normalization quotient limiting balanced frequency values (overall breadth / 4)
    const target = s.length / 4;

    // Numerical logging array to measure occurrences between Q W E R combinations
    // Index map associations : Q=0, W=1, E=2, R=3
    const freq = [0, 0, 0, 0]; 
    const map = { Q: 0, W: 1, E: 2, R: 3 };

    // Baseline frequency scan of structural global parameters
    for (let ch of s) {
        freq[map[ch]]++;
    }

    // Pass gate check for inherent balance needing no subsequent interference
    if (freq[0] === target && freq[1] === target && freq[2] === target && freq[3] === target) {
        return 0;
    }

    let left = 0;           // Trailing Window pointer node
    let ans = s.length;     // Culminating value bounds placeholder

    // Condition parameter checker ensuring all variables adhere strict structural limits:
    // Basically, isolated out-of-block counts are `<= target` consistently 
    const check = () =>
        freq[0] <= target &&
        freq[1] <= target &&
        freq[2] <= target &&
        freq[3] <= target;

    // Mobilize window boundary, symbolically pooling values to substitution cache
    for (let right = 0; right < s.length; right++) {
        // Variable subtraction signaling value enters 'replacable' cache status  
        freq[map[s[right]]]--;

        // Once validation of equilibrium is marked, dynamically contract window size 
        while (left < s.length && check()) {
            // Assess optimized shorter length frame bounds against historic values
            ans = Math.min(ans, right - left + 1);

            // Resurrect variables outside bounding constraints pushing cursor left boundary bounds forwards
            freq[map[s[left]]]++;
            left++;
        }
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) (fixed 4 element map/array)

Links

1234. Replace the Substring for Balanced String (English)1234. 替换子串得到平衡字符串 (Chinese)