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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace All ?'s to Avoid Consecutive Repeating Characters

Number: 1698

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given a string s consisting of lowercase English letters and the '?' character, replace every '?' with a lowercase letter such that the final string does not have any consecutive repeating characters. You must preserve the non-'?' characters and only change the '?' characters. It is guaranteed that apart from '?', the string has no consecutive repeating characters.

Key Insights

  • Replace each '?' independently by trying a small set of candidate letters (e.g., 'a', 'b', 'c') to ensure that the character is different from its immediate neighbors.
  • The left neighbor is already resolved when processing left-to-right; the right neighbor is taken from the original string.
  • Handling consecutive '?' properly is simple by processing them one by one.

Space and Time Complexity

Time Complexity: O(n), where n is the length of string s, since we traverse the string once. Space Complexity: O(n), for constructing the resulting string.

Solution

We iterate through the string from left to right. For each character:

  • If it is not a '?', simply add it to our result.
  • If it is a '?', try letters 'a', 'b', and 'c' (or any set of three letters) until we find one that does not match the last character in our result (if any) and does not equal the next character (if the next character is not a '?'). By choosing a letter that satisfies both conditions, we ensure that no consecutive characters become identical. This greedy approach is sufficient due to the limited alphabet and guarantees provided by the problem.

Code Solutions

# Python solution with line-by-line comments
def modifyString(s: str) -> str:
    # Convert the string to a list to modify it in-place.
    s = list(s)
    n = len(s)
    
    # Iterate over each character in the string.
    for i in range(n):
        # If current character is a '?' replace it
        if s[i] == '?':
            # Try possible characters
            for char in "abc":
                # Check left neighbor if current position i > 0
                if i > 0 and s[i-1] == char:
                    continue
                # Check right neighbor if exists and not a '?'
                if i < n - 1 and s[i+1] == char:
                    continue
                # Found a valid replacement, assign it and break out of loop
                s[i] = char
                break
    # Join the list back into a string and return
    return "".join(s)

# Example usage:
#print(modifyString("?zs"))
← Back to All Questions