LeetCode 1234 - Replace the Substring for Balanced String

The problem asks us to balance a string composed of exactly four types of characters: 'Q', 'W', 'E', and 'R'. A string is balanced when each character occurs exactly n / 4 times, where n is the length of the string.

leetcodemediumstringsliding-window

LeetCode Problem 1234

Difficulty: 🟡 Medium
Topics: String, Sliding Window

Solution

Problem Understanding

The problem asks us to balance a string composed of exactly four types of characters: 'Q', 'W', 'E', and 'R'. A string is balanced when each character occurs exactly n / 4 times, where n is the length of the string. The input is a string s of length n (guaranteed to be a multiple of 4), and the output is the minimum length of a contiguous substring that can be replaced to achieve balance. Replacement can be with any characters of the same length, meaning the substring can be entirely arbitrary, as long as the resulting string becomes balanced.

The constraints 4 <= n <= 10^5 indicate that we need a solution that is at worst linear or linearithmic, as brute-force quadratic solutions will be too slow. Edge cases include strings that are already balanced, strings where one character dominates, or strings where multiple characters exceed their target counts. Since all characters are from a small fixed set, counting occurrences efficiently is feasible with a hash map or fixed-size array.

Approaches

Brute Force Approach: One could consider all possible substrings of s and simulate replacing each substring with characters that would balance the remaining string. For each substring, we would count the occurrences of each character outside that substring and check if replacing the substring could balance the string. While this works in principle, it requires O(n^3) time: O(n^2) for all substrings and O(n) to count the remaining characters for each substring. For n = 10^5, this is infeasible.

Optimal Approach: The key insight is that we only need to replace the excess characters. If a character occurs more than n / 4 times, its extra occurrences must be reduced by replacing a substring containing them. We can use a sliding window to find the smallest substring that contains all excess characters. Outside the window, the counts of all characters must be at most n / 4. We slide the window while maintaining a count of the characters inside it, and for each window, we check if the remaining characters outside are within the target. The minimal window satisfying this condition gives the solution. This is linear time O(n) because each pointer moves at most n steps, and checking counts is constant time since there are only four characters.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check all substrings and simulate replacement; too slow
Optimal O(n) O(1) Sliding window containing all excess characters; uses fixed-size hash map

Algorithm Walkthrough

  1. Count occurrences: Count the frequency of 'Q', 'W', 'E', 'R' in the string s. Compute the allowed frequency target = n / 4.
  2. Identify excess characters: For each character, if its count exceeds target, record the excess amount; if it does not exceed target, treat its excess as zero.
  3. Initialize sliding window: Use two pointers left and right starting at 0. left will mark the start of the window, and right will expand to include characters.
  4. Expand window: Move right through the string, decrementing the excess counts for characters as they are included in the window.
  5. Shrink window: Once all excess counts are zero or negative (meaning all excess characters are inside the window), move left forward to shrink the window as much as possible while maintaining that condition.
  6. Update minimum: Track the minimal window length found that covers all excess characters.
  7. Return result: The length of the smallest window found is the minimal substring length that can be replaced to balance the string.

Why it works: By maintaining the invariant that outside the window, no character exceeds its allowed frequency, we ensure that replacing the window with any arbitrary string will make the overall string balanced. The sliding window guarantees minimality because we always attempt to shrink it from the left once the condition is satisfied.

Python Solution

class Solution:
    def balancedString(self, s: str) -> int:
        from collections import Counter

        n = len(s)
        target = n // 4
        count = Counter(s)
        
        excess = {c: max(0, count[c] - target) for c in 'QWER'}
        if all(v == 0 for v in excess.values()):
            return 0

        min_len = n
        left = 0
        for right, char in enumerate(s):
            if char in excess:
                excess[char] -= 1
            while left <= right and all(v <= 0 for v in excess.values()):
                min_len = min(min_len, right - left + 1)
                if s[left] in excess:
                    excess[s[left]] += 1
                left += 1

        return min_len

Explanation: We first count character frequencies and determine the excess amounts. If all excesses are zero, the string is already balanced. Otherwise, we expand a window with right while decrementing excess counts. Once the condition is met that all excess counts are zero or negative, we attempt to shrink the window from left, updating the minimal length found. Finally, we return the minimal window length.

Go Solution

func balancedString(s string) int {
    n := len(s)
    target := n / 4
    count := map[byte]int{'Q': 0, 'W': 0, 'E': 0, 'R': 0}
    for i := 0; i < n; i++ {
        count[s[i]]++
    }

    excess := map[byte]int{}
    allZero := true
    for _, c := range []byte{'Q', 'W', 'E', 'R'} {
        if count[c] > target {
            excess[c] = count[c] - target
            allZero = false
        } else {
            excess[c] = 0
        }
    }
    if allZero {
        return 0
    }

    minLen := n
    left := 0
    for right := 0; right < n; right++ {
        if _, ok := excess[s[right]]; ok {
            excess[s[right]]--
        }
        for left <= right && excess['Q'] <= 0 && excess['W'] <= 0 && excess['E'] <= 0 && excess['R'] <= 0 {
            if right-left+1 < minLen {
                minLen = right - left + 1
            }
            if _, ok := excess[s[left]]; ok {
                excess[s[left]]++
            }
            left++
        }
    }

    return minLen
}

Go-specific notes: We use a map of bytes for counts, carefully managing subtraction and addition as the window expands and contracts. The condition excess[...] <= 0 is unrolled for all four characters since Go does not allow a direct all() function. Otherwise, the logic mirrors the Python implementation.

Worked Examples

Example 1: s = "QWER"

Step left right excess min_len
Init 0 0 {Q:0,W:0,E:0,R:0} 4
Check - - all zero 0

Output: 0

Example 2: s = "QQWE"

Step left right excess min_len
Init 0 0 {Q:1,W:0,E:0,R:0} 4
right=0(Q) 0 0 {Q:0,W:0,E:0,R:0} 1
Shrink left 1 0 {Q:1,W:0,E:0,R:0} 1

Output: 1

Example 3: s = "QQQW"

Step left right excess min_len
Init 0 0 {Q:2,W:0,E:0,R:0} 4
right=0(Q) 0 0 {Q:1,W:0,E:0,R:0} 4
right=1(Q) 0 1 {Q:0,W:0,E:0,R:0} 2
Shrink left 1 1 {Q:1,W:0,E:0,R:0} 2

Output: 2

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves at most n steps, counting and checking excess is O(1) per step
Space O(1) Fixed-size maps for four characters; constant extra space

The sliding window ensures linear traversal, and since only four character counts are tracked, space does not grow with input size.

Test Cases

# Provided examples
assert Solution().balancedString("QWER") == 0  # already balanced
assert Solution().balancedString("QQWE") == 1  # need to replace 1 Q
assert Solution().balancedString("QQQW")