Replace the Substring for Balanced String - Video Solutions

Problem Overview: You get a string containing only Q, W, E, and R. A string is balanced when each character appears exactly n/4 times. The task is to find the minimum length substring you can replace so the remaining string becomes balanced.

Approach 1: Sliding Window Approach (O(n) time, O(1) space)

This approach uses a frequency counter and a dynamic window to track which substring could be replaced. First count how many times each character appears. Any character exceeding n/4 is considered extra. Expand a right pointer to include characters in the window and decrease their counts from the outside frequency map. Once all remaining characters outside the window satisfy the balanced condition (count[c] ≤ n/4), shrink the window using the left pointer to minimize its length. Because each index moves at most once, the total time complexity is O(n) and the space complexity is O(1). This method relies on the classic sliding window pattern combined with frequency counting.

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

The two-pointer technique frames the same idea more explicitly: maintain left and right pointers that represent the candidate substring to replace. As right moves forward, update counts for characters leaving the "outside" portion of the string. When the outside portion becomes valid (no character exceeds n/4), move left forward to shrink the window while updating the minimum length. This method still scans the string only once and uses a constant-size frequency array because the alphabet is fixed. The approach is closely related to both two pointers and sliding window patterns used in many string optimization problems.

Recommended for interviews: Interviewers expect the Sliding Window solution. A brute force approach that tries all substrings would be O(n^2) and fails for large inputs. Demonstrating the window technique shows you understand how to maintain constraints dynamically while scanning the string in linear time.