algoadvance

You are given a string s that contains only lowercase English letters and the '?' character. The '?' character can be replaced by any lowercase English letter. Replace all the '?' characters such that the final string does not contain any consecutive repeating characters. You must return the final string. If there are multiple solutions, you may return any of them. It is guaranteed an answer exists.

Clarifying Questions

  1. Input Constraints:
    • Is there any size limit for the input string s?
      • Typical constraints apply, usually up to around (10^4) or (10^5) characters.
  2. Character Set:
    • Confirming that the only characters involved are lowercase English letters and '?'.
  3. Output Requirements:
    • Should consecutive repeating replacements be the only concern, ensuring no two adjacent characters are the same?
    • Can we return any valid solution that meets the criteria?

Strategy

  1. Initialization:
    • Convert the string s to a list of characters to allow mutation.
  2. Iterate through the String:
    • Traverse each character in the string.
    • For every '?' found:
      • Consider the adjoining characters (previous and next).
      • Select a replacement character that is different from both adjoining characters.
  3. Replacement Logic:
    • Use a simple loop through the alphabet to find a character that does not match the adjacent ones.
  4. Edge Handling:
    • Handle the boundary cases where '?' is at the start or end.
  5. Complexity Consideration:
    • The solution should be linear ((O(n))), where (n) is the length of the string.

Code

def modifyString(s: str) -> str:
    n = len(s)
    s_list = list(s)
    
    for i in range(n):
        if s_list[i] == '?':
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                if (i > 0 and s_list[i-1] == ch) or (i < n-1 and s_list[i+1] == ch):
                    continue
                s_list[i] = ch
                break

    return ''.join(s_list)

# Example Usage
print(modifyString("??yw?ipkj?"))

Time Complexity

This approach ensures that all questioned characters are replaced by an appropriate letter while guaranteeing no consecutive repeating characters and satisfying the problem constraints.

Try our interview co-pilot at AlgoAdvance.com