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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Replace the Substring for Balanced String

Difficulty: Medium

Problem Description

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.

Key Insights

  • A balanced string contains each character ('Q', 'W', 'E', 'R') exactly n / 4 times.
  • Use a sliding window approach to find the minimum substring that can be replaced to achieve balance.
  • Count the occurrences of each character and determine how many characters need to be replaced for balance.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves counting the occurrences of each character in the string and determining how many characters exceed the required count for balance. A sliding window technique is employed to find the minimum length of a substring that can be replaced to achieve the desired balance. The algorithm maintains a count of characters within the current window and adjusts the window size while checking against the required balance.

Code Solutions

def balancedString(s: str) -> int:
    n = len(s)
    target = n // 4
    count = {char: 0 for char in 'QWER'}
    
    for char in s:
        count[char] += 1
    
    # If already balanced
    if all(x <= target for x in count.values()):
        return 0
    
    left = 0
    min_length = n
    
    for right in range(n):
        count[s[right]] -= 1
        
        while all(count[char] <= target for char in 'QWER'):
            min_length = min(min_length, right - left + 1)
            count[s[left]] += 1
            left += 1
            
    return min_length
← Back to All Questions