Replace Question Marks in String to Minimize Its Value

Medium

Asked by:

23 views

Topics:

StringsGreedy Algorithms

You are given a string s. s[i] is either a lowercase English letter or '?'.

For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i - 1].

The value of t is the sum of cost(i) for all indices i.

For example, for the string t = "aab":

cost(0) = 0
cost(1) = 1
cost(2) = 0
Hence, the value of "aab" is 0 + 1 + 0 = 1.

Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized.

Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.

Example 1:

Input: s = "???"

Output: "abc"

Explanation: In this example, we can replace the occurrences of '?' to make s equal to "abc".

For "abc", cost(0) = 0, cost(1) = 0, and cost(2) = 0.

The value of "abc" is 0.

Some other modifications of s that have a value of 0 are "cba", "abz", and, "hey".

Among all of them, we choose the lexicographically smallest.

Example 2:

Input: s = "a?a?"

Output: "abac"

Explanation: In this example, the occurrences of '?' can be replaced to make s equal to "abac".

For "abac", cost(0) = 0, cost(1) = 0, cost(2) = 1, and cost(3) = 0.

The value of "abac" is 1.

Constraints:

1 <= s.length <= 10⁵
s[i] is either a lowercase English letter or '?'.

Try coding it in LeetCode

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:

What characters are allowed in the string besides question marks?
What is the definition of the string's 'value' that I am trying to minimize?
Can the input string be empty or null?
If multiple valid solutions exist that result in the same minimum value, is any one acceptable?
What is the maximum length of the input string?

Brute Force Solution

Approach

The brute force strategy for this problem involves checking every possible combination of letters that could replace the question marks. It's like trying every possible word to see which one fits best. We generate each possible string and then pick the one that gives us the minimum "value" according to some comparison rule.

Here's how the algorithm would work step-by-step:

Find the first question mark in the string.
Imagine replacing that question mark with the letter 'a'.
Now, instead, imagine replacing it with the letter 'b'.
Then, imagine replacing it with the letter 'c'.
So, for that first question mark, we've tried all three possible letters.
For each of those three possibilities, move to the *next* question mark in the string.
Repeat the process of replacing that question mark with 'a', 'b', and 'c'.
Keep doing this until you've filled in all the question marks for that starting combination.
Now, go back to the very beginning and start again, but this time, try a different combination for the first question mark if you haven't tried them all before.
Continue generating every single possible string that can be created by replacing the question marks with 'a', 'b', and 'c'.
For each completed string, calculate its value based on some rule (like comparing it to strings next to it).
Finally, compare all the values you calculated, and choose the string that resulted in the smallest value.

Code Implementation

def replace_question_marks_brute_force(input_string):
    question_mark_indices = [i for i, char in enumerate(input_string) if char == '?']
    number_of_question_marks = len(question_mark_indices)

    if number_of_question_marks == 0:
        return input_string

    best_string = None
    minimum_string_value = float('inf')

    # Iterate through all possible combinations of replacements.
    def generate_combinations(current_index, current_string):
        nonlocal best_string, minimum_string_value

        if current_index == number_of_question_marks:
            string_value = calculate_string_value(current_string)

            # Compare this string with the best we've seen so far
            if string_value < minimum_string_value:
                minimum_string_value = string_value
                best_string = current_string
            return

        index_to_replace = question_mark_indices[current_index]

        for char in ['a', 'b', 'c']:
            new_string = current_string[:index_to_replace] + char + current_string[index_to_replace + 1:]
            generate_combinations(current_index + 1, new_string)

    generate_combinations(0, input_string)
    return best_string

def calculate_string_value(input_string):
    string_value = 0
    for i in range(len(input_string) - 1):
        if input_string[i] != input_string[i+1]:
            string_value += 1 # Punish different adjacent chars.

    return string_value

Big(O) Analysis

Time Complexity

O(3^q * n) – Let n be the length of the input string and q be the number of question marks in the string. The algorithm explores all possible combinations of replacing each question mark with 'a', 'b', or 'c'. Therefore, there are 3^q possible combinations. For each of these 3^q strings, the algorithm calculates its value, which takes O(n) time in the worst case (as it iterates through the entire string of length n). Thus, the overall time complexity is O(3^q * n).

Space Complexity

O(3^Q) – The brute force algorithm generates every possible string by replacing the question marks. The primary space usage stems from the recursion depth or explicit stack required to manage the branching exploration of each question mark, where Q is the number of question marks in the string. For each question mark, there are three choices ('a', 'b', 'c'), so the algorithm explores 3^Q possibilities, either through recursive calls or by storing intermediate string states. Therefore, the space complexity is O(3^Q), reflecting the exponential growth of possible strings as the number of question marks increases.

Optimal Solution

Approach

We want to fill in the question marks in the string to make it as small as possible alphabetically. We can accomplish this by examining each question mark and picking the smallest letter that doesn't create a duplicate with its immediate neighbors.

Here's how the algorithm would work step-by-step:

Go through the string character by character.
When you find a question mark, consider the letters 'a', 'b', and 'c'.
Check the character directly before the question mark. If it's 'a', then we can't use 'a' to replace the question mark.
Check the character directly after the question mark. If it's 'a', then we can't use 'a' to replace the question mark.
Choose the smallest letter among 'a', 'b', and 'c' that is different from both the characters before and after the question mark.
Replace the question mark with that chosen letter.
If the question mark is at the very beginning or end of the string, only check the character after or before it respectively.

Code Implementation

def replace_question_marks(input_string):
    string_as_list = list(input_string)
    string_length = len(input_string)

    for index in range(string_length):
        if string_as_list[index] == '?':
            # Find the first available character
            for char in 'abc':
                is_valid = True

                # Check the previous character if it exists
                if index > 0 and string_as_list[index - 1] == char:
                    is_valid = False

                # Check the next character if it exists
                if index < string_length - 1 and string_as_list[index + 1] == char:
                    is_valid = False

                if is_valid:
                    string_as_list[index] = char
                    break

    return ''.join(string_as_list)

def replace_question_marks_in_string_to_minimize_its_value(input_string):
    string_as_list = list(input_string)
    string_length = len(input_string)

    for index in range(string_length):
        if string_as_list[index] == '?':
            # Iterate through possible replacement chars 'a', 'b', 'c'
            for replacement_char in 'abc':
                valid_replacement = True

                # Handle the case where we aren't at the beginning of the string
                if index > 0 and string_as_list[index - 1] == replacement_char:
                    valid_replacement = False

                # Handle the case where we aren't at the end of the string
                if index < string_length - 1 and string_as_list[index + 1] == replacement_char:
                    valid_replacement = False

                if valid_replacement:
                    # Assign replacement char and break the loop
                    string_as_list[index] = replacement_char
                    break

    return ''.join(string_as_list)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n character by character. For each character, if it's a question mark, it performs a constant amount of work: checking at most two adjacent characters and choosing a replacement from 'a', 'b', and 'c'. Since the amount of work done per character is constant and independent of n, the overall time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input string in-place, modifying it directly. It only uses a few constant space variables to store the current character and potentially the characters before and after the question mark. The amount of extra space used does not scale with the input string's length N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on requirements.
String consisting only of question marks	Iteratively replace with 'a', 'b', 'c' avoiding adjacent repetition.
String with a single character, which is a question mark	Replace the question mark with 'a'.
String with no question marks	Return the original string as is.
Question mark at the beginning of the string	Replace with a character different than the subsequent character.
Question mark at the end of the string	Replace with a character different than the preceding character.
Consecutive question marks in the string	Iteratively replace, ensuring each replacement differs from its neighbors.
Long string to consider performance implications	The linear time complexity of the iterative replacement ensures reasonable performance.

Null or empty input string

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on requirements.

String consisting only of question marks

How to Handle:

Iteratively replace with 'a', 'b', 'c' avoiding adjacent repetition.

String with a single character, which is a question mark

How to Handle:

Replace the question mark with 'a'.

String with no question marks

How to Handle:

Return the original string as is.

Question mark at the beginning of the string

How to Handle:

Replace with a character different than the subsequent character.

Question mark at the end of the string

How to Handle:

Replace with a character different than the preceding character.

Consecutive question marks in the string

How to Handle:

Iteratively replace, ensuring each replacement differs from its neighbors.

Long string to consider performance implications

How to Handle:

The linear time complexity of the iterative replacement ensures reasonable performance.