涂改笔
测试数据来自 system/2253
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
时间限制:1秒 内存限制:256M
【题目描述】
有两个长度都为N的字符串 \(S\) 和 \(T\),他们只包含两种字母:M 和 Y。
小H有一支特殊的涂改笔,每次可以将字符串的一个子串进行涂改,涂改之后子串中的字母 M 会变为 Y, 字母 Y 会变为 M。
那么要将字符串 \(T\) 涂改成字符串 \(S\),最少需要涂改多少次?请你编程回答。
【输入格式】
输入包含三行:
第一行是整数 \(N\),表示字符串的长度。
第二行是字符串 \(S\)。
第三行是字符串 \(T\)。
【输出格式】
一个整数,表示将 \(T\) 涂改成 \(S\) 需要的最少涂改次数。
【输入输出样例】
Input
7
YMMMYMM
MMYYYMM
Output
2
【输出样例解释】
第一次只需把符串 \(T\) 的第一个字符 M 涂改诚 Y,得到 YMYYYMM。
第二次,可以把 \(T\) 的第三个和第四个字符 YY 涂改诚 MM,得到 YMMMYMM,即字符串 \(S\)。
当然,可能还有其他方式,但涂改次数至少需要 2 次。
【数据限制】
对于 \(100\%\) 的数据, \(1≤N≤1000\)。
【来源】
Mr.he