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.
Example 1:
Input: s = "QWER" Output: 0 Explanation: s is already balanced.
Example 2:
Input: s = "QQWE" Output: 1 Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
Example 3:
Input: s = "QQQW" Output: 2 Explanation: We can replace the first "QQ" to "ER".
Constraints:
n == s.length4 <= n <= 105n is a multiple of 4.s contains only 'Q', 'W', 'E', and 'R'.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force strategy for balancing a string involves checking every possible substring replacement. We will examine each possible substring within the larger string and determine if replacing it leads to a balanced string.
Here's how the algorithm would work step-by-step:
def replace_substring_brute_force(input_string):
string_length = len(input_string)
min_length = float('inf')
for substring_length in range(1, string_length + 1):
for start_index in range(string_length - substring_length + 1):
# Iterate through all possible substrings of current length
end_index = start_index + substring_length
substring_to_replace = input_string[start_index:end_index]
for i in range(4**substring_length):
replacement_string = ""
temp_index = i
for _ in range(substring_length):
remainder = temp_index % 4
if remainder == 0:
replacement_string = 'Q' + replacement_string
elif remainder == 1:
replacement_string = 'W' + replacement_string
elif remainder == 2:
replacement_string = 'E' + replacement_string
else:
replacement_string = 'R' + replacement_string
temp_index //= 4
new_string = input_string[:start_index] + replacement_string + input_string[end_index:]
counts = {
'Q': 0,
'W': 0,
'E': 0,
'R': 0
}
for char in new_string:
counts[char] += 1
# Check if the string is balanced after replacement
if all(counts[char] == string_length / 4 for char in counts):
min_length = min(min_length, substring_length)
# Update if the current substring is shorter
break
# Return 0 if no balanced string can be found
if min_length == float('inf'):
return 0
return min_lengthThe key is to find the smallest section of the string we can change to balance the counts of each character. We can efficiently locate this section by focusing on what's 'extra' and using a clever shrinking window approach.
Here's how the algorithm would work step-by-step:
def balancedString(input_string: str) -> int:
string_length = len(input_string)
expected_count = string_length // 4
char_counts = {
'Q': 0,
'W': 0,
'E': 0,
'R': 0
}
for char in input_string:
char_counts[char] += 1
excess_counts = {
char: count - expected_count for char, count in char_counts.items() if count > expected_count
}
# If already balanced, no replacement needed
if all(count <= expected_count for count in char_counts.values()):
return 0
min_length = string_length
window_start = 0
window_counts = {
'Q': 0,
'W': 0,
'E': 0,
'R': 0
}
for window_end in range(string_length):
window_counts[input_string[window_end]] += 1
# Shrink the window from the left
while all(window_counts[char] >= excess_counts.get(char, 0) for char in ['Q', 'W', 'E', 'R']):
min_length = min(min_length, window_end - window_start + 1)
# Try shrinking from the left to optimize
window_counts[input_string[window_start]] -= 1
window_start += 1
return min_length| Case | How to Handle |
|---|---|
| Null or empty input string | Return 0 if the input string is null or empty, as no replacement is possible. |
| String length not divisible by 4 | Return 0 immediately, as a balanced string must have a length divisible by 4. |
| String is already balanced | Return 0, as no replacement is needed. |
| String contains characters other than 'Q', 'W', 'E', 'R' | Throw an IllegalArgumentException since the problem statement only allows these characters. |
| String with only one distinct character | Handle the case where a single character dominates, potentially requiring a large replacement to balance. |
| Large string exceeding memory limits | Ensure the sliding window approach used does not require storing the entire string in memory at once. |
| No substring can be found to balance the string | If the sliding window completes and no valid substring is found, return the length of the original string. |
| Integer overflow when calculating counts | Use appropriate data types (e.g., int) and check for potential overflow issues when incrementing counts for characters. |