Overview

This problem asks you to compare Takahashi’s answer string \(S\) with the correct answer string \(T\), and find the minimum number of rewrites needed to reduce the number of incorrect answers to at most \(K\).

Analysis

The key insight for solving this problem is that “each rewrite can reduce the number of incorrect answers by at most 1.”

Since we want to minimize the number of rewrites, there is no need to rewrite problems that are already correct (where the characters in \(S\) and \(T\) match). The optimal strategy is to pinpoint only the incorrect problems (where the characters in \(S\) and \(T\) differ) and rewrite them to the correct answer.

First, count the number of incorrect answers in the initial state before any rewrites. Let this be \(D\). - If \(D \leq K\): The number of incorrect answers is already within the allowed range, so no rewrites are needed. The answer is \(0\). - If \(D > K\): We need to rewrite incorrect problems to correct answers until the number of incorrect answers becomes \(K\). The required number of rewrites is \(D - K\).

Therefore, the answer can be obtained by the simple calculation \(\max(0, D - K)\).

Algorithm

1. Compare characters at the same positions in strings \(S\) and \(T\) from the beginning, and count the number of differing characters (the initial number of incorrect answers). Let this be diff_count.
2. Compute diff_count - K, and if the value is negative, set it to \(0\) (in formula: \(\max(0, \text{diff\_count} - K)\)).
3. Output the computed value.

Complexity

• Time complexity: \(O(N)\) We only need to scan and compare strings \(S\) and \(T\) of length \(N\) once from the beginning, so it is \(O(N)\). This easily fits within the time limit even for the constraint \(N \leq 10^6\).
• Space complexity: \(O(N)\) We use \(O(N)\) space to store strings \(S\) and \(T\) of length \(N\) in memory.

Implementation Notes

• In Python, using zip(S, T) allows you to very concisely write the process of simultaneously extracting and comparing characters at the same positions in two strings.

• Since the input size can be as large as \(10^6\), using sys.stdin.read().split() instead of the standard input() can speed up input reading and reduce the risk of TLE (Time Limit Exceeded).

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    S = input_data[2]
    T = input_data[3]
    
    diff_count = sum(s != t for s, t in zip(S, T))
    
    ans = max(0, diff_count - K)
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.