Taro Logo

Replace the Substring for Balanced String

Medium
Asked by:
Profile picture
64 views
Topics:
ArraysStringsTwo PointersSliding Windows

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.length
  • 4 <= n <= 105
  • n is a multiple of 4.
  • s contains only 'Q', 'W', 'E', and 'R'.

Solution


Clarifying Questions

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:

  1. What is the maximum length of the input string `s`?
  2. What characters can the string `s` contain, and is it limited to just 'Q', 'W', 'E', and 'R'?
  3. If the string is already balanced, should I return 0, or is there a different expected output?
  4. If multiple substrings of the same minimum length can balance the string, can I return any one of them?
  5. Is there a specific data type I should use for the return value (e.g., int, long), and can I assume the length of the string will always be within the bounds of a standard integer type?

Brute Force Solution

Approach

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:

  1. First, look at every possible small piece of the string, starting with the very first character.
  2. Then, consider slightly bigger pieces, shifting one character to the right each time.
  3. Keep increasing the size of the piece you're looking at, and moving it along the string, until you've checked every single possible piece.
  4. For each of these pieces, imagine that you take it out and replace it with something else.
  5. Try every possible replacement for each piece, seeing if the resulting string is now balanced.
  6. If a replacement makes the string balanced, remember how big the piece was that you replaced.
  7. Finally, after you've checked all pieces and all replacements, choose the smallest piece that made the string balanced.

Code Implementation

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_length

Big(O) Analysis

Time Complexity
O(n³) – The brute force approach iterates through all possible substrings, which requires nested loops. The outer loop iterates n times, and the inner loop iterates up to n times, resulting in O(n²) substring combinations. For each substring, we consider all possible replacements. In the worst case, we might iterate through all possible characters in the alphabet for each position in the substring, which, for the longest substring length of n, could take O(n) time. Therefore, the overall time complexity is O(n² * n) = O(n³).
Space Complexity
O(1) – The brute force approach, as described, primarily involves iterating through substrings and checking replacements. The algorithm doesn't explicitly mention auxiliary data structures that scale with input string size N. There's no mention of storing substring combinations, visited states, or intermediate results in a way that grows beyond a constant amount. Therefore, the auxiliary space required is constant, independent of the string length N.

Optimal Solution

Approach

The 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:

  1. First, figure out how many of each character we *should* have in a balanced string.
  2. Then, count how many of each character we *actually* have in the string.
  3. Determine the *excess* of each character: the difference between what we have and what we should have.
  4. Now, imagine a window moving across the string. We want to find the smallest window that contains at least the excess amount of each overrepresented character.
  5. Start with a tiny window at the beginning and expand it until it contains enough of each character to compensate for the excesses we found earlier.
  6. Once we have a valid window, try shrinking it from the left while still maintaining enough of each necessary character.
  7. Keep track of the smallest valid window you find. That's the section you need to replace to balance the string.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – The solution iterates through the string once to count character frequencies and determine the excess of each character. Then, a sliding window approach is used to find the smallest substring to replace. The window expands and contracts, but each character in the string is visited at most twice (once by the right pointer and once by the left pointer). Therefore, the overall time complexity is O(n), where n is the length of the string.
Space Complexity
O(1) – The algorithm uses a fixed number of variables to store the required character counts and the excess counts. Specifically, we need space for counts of each character ('Q', 'W', 'E', 'R'), and their excesses, which amounts to a constant amount of extra space, irrespective of the input string length N. Thus, the auxiliary space used is independent of the input size, resulting in O(1) space complexity.

Edge Cases

Null or empty input string
How to Handle:
Return 0 if the input string is null or empty, as no replacement is possible.
String length not divisible by 4
How to Handle:
Return 0 immediately, as a balanced string must have a length divisible by 4.
String is already balanced
How to Handle:
Return 0, as no replacement is needed.
String contains characters other than 'Q', 'W', 'E', 'R'
How to Handle:
Throw an IllegalArgumentException since the problem statement only allows these characters.
String with only one distinct character
How to Handle:
Handle the case where a single character dominates, potentially requiring a large replacement to balance.
Large string exceeding memory limits
How to Handle:
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
How to Handle:
If the sliding window completes and no valid substring is found, return the length of the original string.
Integer overflow when calculating counts
How to Handle:
Use appropriate data types (e.g., int) and check for potential overflow issues when incrementing counts for characters.