Overview

This problem asks you to compare two strings written in Takahashi’s and Aoki’s notebooks, generate a restoration result according to the rules described in the problem statement, and determine whether there are any contradictions.

Analysis

For each character position, we compare the characters in \(S\) and \(T\) to determine the restoration result. The key observation is to properly handle the following four cases: 1. Both characters are the same (lowercase letter or ?): adopt that character 2. One is ? and the other is a lowercase letter: adopt the lowercase letter 3. Both are ?: adopt ? 4. Both are lowercase letters but different: adopt ! to indicate a contradiction

A straightforward approach of comparing each position character by character is sufficient. Since \(N\) is at most \(5 \times 10^5\), this can be efficiently handled with a simple loop.

Algorithm

1. Read the input: string length \(N\), string \(S\), and string \(T\).
2. Initialize a list res to store the result and a flag has_error to indicate the presence of contradictions.
3. For each index \(i\) (\(0 \leq i < N\)), do the following:
   • If \(S[i]\) and \(T[i]\) are equal:
     • If both are ?, append ? to the result
     • Otherwise (lowercase letter), append that character
   • If they are not equal:
     • If \(S[i]\) is ?, append \(T[i]\) (a lowercase letter)
     • If \(T[i]\) is ?, append \(S[i]\) (a lowercase letter)
     • If both are lowercase letters but different, append ! and set has_error to True
4. Generate and output the result string. Output “Yes” if has_error is True, otherwise output “No”.

Complexity

• Time complexity: \(O(N)\)
  • Each character is processed exactly once
• Space complexity: \(O(N)\)
  • A list is needed to store the result string

Implementation Notes

• Use if-else branching for each case, processing according to the rules.

• Use a flag to track whether a contradiction (!) has occurred at least once.

• For efficient string concatenation, append to a list and use join at the end.

  Source Code

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0].strip())
    S = data[1].strip()
    T = data[2].strip()
    
    res = []
    has_error = False
    
    for i in range(n):
        s_char = S[i]
        t_char = T[i]
        
        if s_char == t_char:
            if s_char == '?':
                res.append('?')
            else:
                res.append(s_char)
        else:
            if s_char == '?':
                res.append(t_char)
            elif t_char == '?':
                res.append(s_char)
            else:
                res.append('!')
                has_error = True
                
    result_str = ''.join(res)
    print(result_str)
    print("Yes" if has_error else "No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.