Overview

This problem asks us to rewrite Takahashi’s answer \(S\) the minimum number of times so that the number of mismatches (incorrect answers) compared to the correct answer \(T\) is at most \(K\).

Analysis

Key Insight: Distinguishing Between Two Types of Rewrites

For each position \(i\) in \(S\), the relationship between \(S[i]\) and \(T[i]\) falls into one of two patterns:

• Matching positions: \(S[i] = T[i]\) (already correct)
• Mismatching positions: \(S[i] \neq T[i]\) (incorrect)

Let \(W\) (number of Wrong answers) denote the total number of mismatching positions.

Thinking About the Effect of Rewrites

A rewrite operation is “changing a character in \(S\)”, but its effect differs depending on the position:

1. Rewriting a mismatching position (fixing): At a position where \(S[i] \neq T[i]\), change \(S[i]\) to \(T[i]\) → incorrect answers decrease by 1, rewrite cost 1
2. Rewriting a matching position (worsening): At a position where \(S[i] = T[i]\), change \(S[i]\) to something else → incorrect answers increase by 1, rewrite cost 1
3. Changing a mismatching position to a different wrong answer: At a position where \(S[i] \neq T[i]\), change it to a value that is neither the original nor \(T[i]\) → incorrect count stays the same, rewrite cost 1 (pointless)

Since we want to reduce the number of incorrect answers, it’s clear that we only need to use Pattern 1 (fixing mismatching positions to the correct answer). There is no reason to worsen answers or make meaningless changes.

Required Number of Rewrites

The current number of incorrect answers is \(W\), and we want it to be at most \(K\):

• If \(W \leq K\), the condition is already satisfied, so 0 rewrites are needed
• If \(W > K\), we need to reduce the incorrect answers by \(W - K\), and since each fix reduces the count by 1, the number of rewrites is \(W - K\)

Therefore, the answer is \(\max(0, W - K)\).

Concrete Example

For \(N = 5, K = 1, S = \) 10110, \(T = \) 01100:

Position	1	2	3	4	5
\(S\)	1	0	1	1	0
\(T\)	0	1	1	0	0
Match?	✗	✗	✓	✗	✓

There are \(W = 3\) mismatches. To get this down to \(K = 1\) or fewer, \(3 - 1 = 2\) rewrites are needed.

Algorithm

1. Compare \(S\) and \(T\) character by character and count the number of mismatches \(W\)
2. Output \(\max(0, W - K)\)

Complexity

• Time complexity: \(O(N)\) (just a single scan through the strings)
• Space complexity: \(O(N)\) (for storing strings \(S, T\))

Implementation Notes

• Although \(N\) can be as large as \(10^6\), \(O(N)\) is more than sufficient.

• In Python, you can concisely count the number of mismatches using a generator expression like sum(1 for i in range(N) if S[i] != T[i]).

• Make sure not to forget max(0, ...) to avoid a negative answer when \(W \leq K\).

  Source Code

N, K = map(int, input().split())
S = input()
T = input()

# Count the number of positions where S and T differ
wrong = sum(1 for i in range(N) if S[i] != T[i])

# We need to reduce wrong to at most K
# Each fix (changing S[i] to T[i] where they differ) reduces wrong by 1 and costs 1 edit
# We need max(0, wrong - K) fixes
print(max(0, wrong - K))

---

This editorial was generated by claude4.6opus-thinking.