We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Replace All ?'s to Avoid Consecutive Repeating Characters

Difficulty: Easy

Problem Description

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. 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.

Key Insights

  • Each '?' can be replaced by any lowercase letter.
  • The replacement must ensure that no two adjacent characters are the same.
  • We can determine the character to replace '?' based on its neighboring characters.
  • A greedy approach can be used to select valid characters.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be solved using a greedy approach where we iterate through the string. For each '?' encountered, we will check the preceding and succeeding characters (if they exist) to determine a valid character that can replace the '?'. We'll choose a character from 'a' to 'z' that is not equal to the adjacent characters. This ensures that we avoid creating consecutive repeating characters.

Code Solutions

def replaceQuestionMarks(s: str) -> str:
    s = list(s)  # Convert string to list for mutability
    n = len(s)

    for i in range(n):
        if s[i] == '?':
            for char in 'abcdefghijklmnopqrstuvwxyz':
                # Check adjacent characters
                if (i > 0 and s[i - 1] == char) or (i < n - 1 and s[i + 1] == char):
                    continue
                s[i] = char  # Replace '?' with a valid character
                break  # Exit the loop once a valid character is found

    return ''.join(s)  # Convert list back to string
← Back to All Questions