Overview

This problem asks you to compare two strings \(S\) and \(T\) at each corresponding position, construct a restored string according to the given rules, and determine whether any contradiction (!) occurs.

Analysis

Each position \(i\) is determined independently of other positions. That is, the restored result at position \(i\) is uniquely determined by looking at only the two characters \(S[i]\) and \(T[i]\), and the overall solution simply repeats this \(N\) times.

The key observation is that the following 4-case breakdown directly becomes the solution procedure:

• Same lowercase letters: confirmed as that character (e.g., a and a → a)
• One is ?: adopt the other lowercase letter (e.g., ? and b → b)
• Both are ?: unknown, so it stays as ? (e.g., ? and ? → ?)
• Different lowercase letters: impossible to determine which is correct, so ! (e.g., c and d → !)

A naive approach of “guessing the entire original board writing and searching for a consistent string” would result in an exponential number of candidates and is impractical (TLE). However, since the restoration rule is determined independently at each position, no search is needed, and the problem can be solved with a simple single pass.

Algorithm

1. Prepare a result array res of length \(N\) and a contradiction flag has_conflict=False.
2. For \(i=1..N\), examine \((S[i], T[i])\) and determine res[i] as follows:
   • If \(S[i] == T[i]\), then res[i]=S[i] (this also covers the case where both are ?)
   • Otherwise, if \(S[i]=='?'\), then res[i]=T[i]
   • Otherwise, if \(T[i]=='?'\), then res[i]=S[i]
   • Otherwise (different lowercase letters), set res[i]='!' and has_conflict=True
3. Concatenate res to output the restored string, and output Yes if has_conflict is True, otherwise output No.

(Example) - When \(S=\text{"a?c"}\), \(T=\text{"ab?"}\): - 1st character: a and a → a - 2nd character: ? and b → b - 3rd character: c and ? → c The restored result is "abc", and since there is no contradiction, output No.

Complexity

• Time complexity: \(O(N)\) (each position is processed once)
• Space complexity: \(O(N)\) (to store the restored string)

Implementation Notes

• Since \(N\) can be as large as \(5 \times 10^5\), concatenating strings one character at a time with += can be slow. It is safer to append to an array (list) and use ''.join(res) at the end.

• Since the input is also large, using sys.stdin.buffer.read() allows for faster reading.

• The \(S[i]==T[i]\) branch naturally handles the case where both are ? (? and ?).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().splitlines()
    n = int(data[0])
    s = data[1].decode()
    t = data[2].decode()

    res = [''] * n
    has_conflict = False

    for i, (a, b) in enumerate(zip(s, t)):
        if a == b:
            res[i] = a
        elif a == '?':
            res[i] = b
        elif b == '?':
            res[i] = a
        else:
            res[i] = '!'
            has_conflict = True

    sys.stdout.write(''.join(res) + '\n' + ('Yes' if has_conflict else 'No'))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.