Naive Approach

A brute-force approach would involve iterating through all possible substrings and, for each substring, checking if replacing it would result in a balanced string. This would involve counting the occurrences of each character (Q, W, E, R) in the modified string and verifying if each count equals n / 4.

Code (Python)

def is_balanced(s):
    n = len(s)
    if n % 4 != 0:
        return False
    
    target_count = n // 4
    counts = {"Q": 0, "W": 0, "E": 0, "R": 0}
    for char in s:
        counts[char] += 1
        
    for char in counts:
        if counts[char] != target_count:
            return False
            
    return True

def min_replacement_brute_force(s):
    n = len(s)
    min_len = n  # Initialize with maximum possible length

    if is_balanced(s):
        return 0

    for i in range(n):
        for j in range(i, n):
            sub_len = j - i + 1
            
            # Iterate through all possible replacements
            for replacement_index in range(4**sub_len):
                temp_replacement = ""
                temp = replacement_index
                for _ in range(sub_len):
                    remainder = temp % 4
                    if remainder == 0:
                        temp_replacement = "Q" + temp_replacement
                    elif remainder == 1:
                        temp_replacement = "W" + temp_replacement
                    elif remainder == 2:
                        temp_replacement = "E" + temp_replacement
                    else:
                        temp_replacement = "R" + temp_replacement
                    temp //= 4

                temp_s = list(s)
                temp_s[i:j+1] = list(temp_replacement)
                temp_s = "".join(temp_s)
                
                if is_balanced(temp_s):
                    min_len = min(min_len, sub_len)

    return min_len

Time Complexity

O(n^3 * 4^n), where n is the length of string s.

Space Complexity

O(n)

Optimal Approach: Sliding Window

The optimal approach uses a sliding window technique. We first count the occurrences of each character in the string. We then determine the excess count of each character (i.e., how many more times it appears than n / 4). The sliding window then aims to find the smallest substring that contains at least these excess counts.

Algorithm

1. Count the occurrences of each character (Q, W, E, R).
2. Calculate the need for each character, i.e., how many extra occurrences there are above n / 4.
3. Use a sliding window to find the minimum length substring that contains all the needed characters.

Code (Python)

def balanced_string(s):
    n = len(s)
    k = n // 4
    count = {"Q": 0, "W": 0, "E": 0, "R": 0}
    for c in s:
        count[c] += 1

    need = {"Q": max(0, count["Q"] - k), "W": max(0, count["W"] - k), 
            "E": max(0, count["E"] - k), "R": max(0, count["R"] - k)}

    if sum(need.values()) == 0:
        return 0

    l, r = 0, 0
    min_len = n
    window_count = {"Q": 0, "W": 0, "E": 0, "R": 0}

    while r < n:
        window_count[s[r]] += 1
        while all(window_count[char] >= need[char] for char in need):
            min_len = min(min_len, r - l + 1)
            window_count[s[l]] -= 1
            l += 1
        r += 1

    return min_len

Time Complexity

O(n), where n is the length of the string s.

Space Complexity

O(1), because we only store counts for the four characters (Q, W, E, R).

Edge Cases

• If the string is already balanced, return 0.
• The input string will always have a length that is a multiple of 4.