Replace All ?'s to Avoid Consecutive Repeating Characters

Easy

Asked by:

0 views

Topics:

Strings

Given a string s containing only lowercase English letters and the '?' character, convert all the '?' characters into lowercase letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non '?' characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Constraints:

1 <= s.length <= 100
s consist of lowercase English letters and '?'.

Replace All ?'s to Avoid Consecutive Repeating Characters

Easy

Asked by:

0 views

Topics:

Strings

Given a string s containing only lowercase English letters and the '?' character, convert all the '?' characters into lowercase letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non '?' characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Constraints:

1 <= s.length <= 100
s consist of lowercase English letters and '?'.

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 is the maximum length of the input string `s`?
Besides lowercase English letters and '?', are there any other characters that could appear in the input string?
If there are multiple possible valid replacement strings, is any one acceptable, or is there a specific criteria for choosing among them?
Is the input string guaranteed to be valid, meaning that any non-'?' characters are not consecutive repeats?
Can the input string be empty or null?

Brute Force Solution

Approach

The brute force method for this problem is to try every possible character ('a', 'b', or 'c') in place of each question mark. We then check if any adjacent characters are the same after making each replacement. If they are, we discard that possibility and try another.

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

Look at the input, and find the first question mark.
Replace that question mark with the letter 'a'.
Now, check if the new letter 'a' is the same as the letter before it or the letter after it.
If it is the same as either of those letters, discard this possibility and instead replace the question mark with the letter 'b'.
If 'b' also fails (because it's the same as the letters next to it), try the letter 'c'.
If 'c' also fails, then there's no solution for the initial input.
Once you find a letter that works for the first question mark, move on to the next question mark and repeat the process of trying 'a', 'b', and 'c'.
Keep doing this for every question mark in the input.
If you manage to fill in all the question marks without creating any adjacent repeating characters, then you've found a solution.

Code Implementation

def replace_question_marks_brute_force(input_string):
    string_list = list(input_string)
    length_of_string = len(string_list)

    def solve(index):
        if index == length_of_string:
            return ''.join(string_list)

        if string_list[index] != '?':
            return solve(index + 1)

        for char in 'abc':
            string_list[index] = char

            # Check if the new character causes adjacent repeats
            is_valid = True
            if index > 0 and string_list[index] == string_list[index - 1]:
                is_valid = False
            if index < length_of_string - 1 and string_list[index] == string_list[index + 1]:
                is_valid = False

            if is_valid:
                result = solve(index + 1)
                if result:
                    return result

        # Backtrack: Reset the character if no solution found
        string_list[index] = '?'
        return None

    return solve(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(3^n) – The algorithm iterates through the string of length n. For each '?' character, it explores three possibilities ('a', 'b', 'c'). In the worst-case scenario, where all characters are '?', the algorithm essentially explores all possible combinations of 'a', 'b', and 'c' for each position. This results in a branching factor of 3 for each '?' which can be up to n times. Therefore, the time complexity is O(3^n).

Space Complexity

O(N) – The provided brute force approach, as described, inherently involves recursion or a call stack depth proportional to the number of question marks, N, in the input string. In the worst-case scenario, every character could be a question mark, requiring the algorithm to explore a tree of possibilities. Each level of recursion stores the state of the string and the current position, leading to auxiliary space usage that grows linearly with the number of question marks. Therefore, the space complexity is O(N), where N is the length of the input string containing question marks.

Optimal Solution

Approach

The goal is to fill question marks with letters so that no two adjacent letters are the same. We can solve this by going through the string and, whenever we see a question mark, choosing a letter that's different from its neighbors.

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

Go through the string from beginning to end, one character at a time.
If the current character is not a question mark, skip it and move to the next character.
If the current character is a question mark, look at the characters before and after it.
Choose a letter (like a, b, or c) that is different from both the character before and the character after the question mark. This makes sure you don't have repeating letters next to each other.
Replace the question mark with the chosen letter.
Move to the next character and repeat until you reach the end of the string.

Code Implementation

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

    for index in range(string_length):
        if string_as_list[index] == '?':
            # Determine neighbors; default to empty string if out of bounds.
            previous_character = string_as_list[index - 1] if index > 0 else ''

            next_character = string_as_list[index + 1] if index < string_length - 1 else ''

            # Find a character that is different from its neighbors.
            for char_to_try in 'abc':
                if char_to_try != previous_character and char_to_try != next_character:
                    # Replace the question mark; break since a valid char found.
                    string_as_list[index] = char_to_try
                    break

    return ''.join(string_as_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, examining each character. When a '?' is encountered, it performs a constant number of comparisons (at most two) to determine a suitable replacement character (a, b, or c). Therefore, the time complexity is directly proportional to the length of the string, denoted as n, making it O(n).

Space Complexity

O(1) – The algorithm iterates through the input string in place, modifying the string directly. It only uses a few constant space variables to store the current character's neighbors during the replacement process. The space used does not depend on the length of the string, denoted as N, thus making it constant space. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string or throw an IllegalArgumentException, depending on requirements
String with single '?' character	Replace it with 'a' since there are no adjacent characters to consider
String with two '?' characters at the beginning	Replace the first with 'a' and the second with 'b' to avoid consecutive repeating characters
String with two '?' characters at the end	Replace the second to last with a char that is not the previous one, and the last with a char that is not the second to last
String with consecutive '?' characters in the middle	Iterate through and replace each '?' ensuring that it's different from its adjacent characters
String with '?' character at the beginning followed by a non-'?' character	Replace the '?' with a character that's different from the following character
String with '?' character at the end preceded by a non-'?' character	Replace the '?' with a character that's different from the preceding character
Long string with many '?' characters, performance considerations	An iterative approach is generally more efficient than recursion and avoids stack overflow errors with long inputs.