/ Vijos / 题库 /

涂改笔

涂改笔

时间限制: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

信息

ID
2253
难度
9
分类
模拟 | 字符串 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
5
上传者