We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace the Substring for Balanced String

Number: 1351

Difficulty: Medium

Paid? No

Companies: Accolite, Amazon

Problem Description

Given a string s of length n containing only the characters 'Q', 'W', 'E', and 'R', a string is balanced if each character appears exactly n/4 times. The task is to find the minimum length of a contiguous substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.

Key Insights

  • Count the frequency of each character in the string.
  • Determine the excess count for characters that appear more than n/4 times.
  • Use a sliding window to identify the smallest substring such that when replaced, the rest of the string meets the balance criteria.
  • If the string is already balanced (i.e., all counts are exactly n/4), the answer is 0.
  • The sliding window approach ensures we find the minimum replacement window efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (only using a fixed-size dictionary/array for 4 characters)

Solution

The solution first calculates the count of each character and checks for excess above the target (n/4). Using a sliding window, we progressively reduce the count of characters as we move the right pointer. When the remaining characters (outside the window) satisfy the balance requirement (each count is ≤ n/4), the current window is a valid candidate for replacement. Then, we try to shrink this window from the left to find the minimum possible length that still meets the valid condition. This minimum length is the answer.

Code Solutions

# Python solution for the problem

def balancedString(s):
    n = len(s)
    target = n // 4
    # Count frequency of characters
    count = {'Q': 0, 'W': 0, 'E': 0, 'R': 0}
    for ch in s:
        count[ch] += 1

    # If already balanced, no replacement needed
    if all(count[ch] == target for ch in "QWER"):
        return 0

    min_len = n
    left = 0
    
    # Use sliding window technique
    for right in range(n):
        count[s[right]] -= 1
        # Check if the remaining string (outside the window) is balanced
        while left < n and all(count[ch] <= target for ch in "QWER"):
            min_len = min(min_len, right - left + 1)
            count[s[left]] += 1
            left += 1
    return min_len

# Example usage:
print(balancedString("QWER"))  # Output: 0
print(balancedString("QQWE"))  # Output: 1
print(balancedString("QQQW"))  # Output: 2
← Back to All Questions