Overview

This is a problem where you compare Takahashi’s and Aoki’s notes to reconstruct the original string. You need to determine whether there are any contradictions (positions where both notes have different characters).

Analysis

In this problem, we compare the two strings \(S\) and \(T\) character by character and construct a new string according to the rules. The important four cases are:

1. Both are ? → Cannot be reconstructed, so ?
2. One is ? and the other is a lowercase letter → Adopt the lowercase letter
3. Both are the same lowercase letter → Adopt that character
4. Both are different lowercase letters → Contradiction, so !

Simply performing these checks straightforwardly is fast enough to solve the problem. No special tricks are needed — just a single pass through the loop is sufficient.

Algorithm

1. For each index \(i\), compare \(S[i]\) and \(T[i]\).
2. Determine the reconstructed character according to the four conditions above.
3. If a contradiction (!) appears even once, set a flag.
4. Finally, output the reconstructed string and whether a contradiction exists.

For example, given the following input:

5
a?c?e
?b?d?

• 1st character: a vs ? → a
• 2nd character: ? vs b → b
• 3rd character: c vs ? → c
• 4th character: ? vs d → d
• 5th character: e vs ? → e

The result is "abcde", with no contradiction (No).

Complexity

• Time complexity: \(O(N)\)
  Each character is examined only once, so it runs in linear time.
• Space complexity: \(O(N)\)
  A list is needed to store the resulting string.

Implementation Notes

• In Python, using + for string concatenation can be slow, so it is better to store characters in a list first and then join them at the end with ''.join().

• For managing the contradiction flag, simply set it to True at the moment ! is appended.

  Source Code

N = int(input())
S = input()
T = input()

result = []
has_contradiction = False

for i in range(N):
    char_s = S[i]
    char_t = T[i]
    
    if char_s == '?' and char_t == '?':
        result.append('?')
    elif char_s == '?':
        result.append(char_t)
    elif char_t == '?':
        result.append(char_s)
    elif char_s == char_t:
        result.append(char_s)
    else:
        result.append('!')
        has_contradiction = True

print(''.join(result))
if has_contradiction:
    print("Yes")
else:
    print("No")

---

This editorial was generated by qwen3-coder-480b.