AT_abc399_e.[ABC399E] Replace

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个正整数 NN 以及两个长度为 NN 的小写英文字母字符串 SS 和 TT。
请判断是否可以通过重复以下操作(允许 0 次操作)将 SS 变为 TT。若可能,还需输出所需的最小操作次数。

操作:
选择两个小写英文字母 xx 和 yy,将 SS 中 所有 出现的 xx 替换为 yy。

输入格式

输入通过标准输入给出,格式如下:

NN
SS
TT

输出格式

若可以将 SS 变为 TT,则输出所需的最小操作次数;否则输出 −1-1。

输入输出样例

  • 输入#1

    6
    afbfda
    bkckbb

    输出#1

    4
  • 输入#2

    4
    abac
    abac

    输出#2

    0
  • 输入#3

    4
    abac
    abrc

    输出#3

    -1
  • 输入#4

    4
    abac
    bcba

    输出#4

    4

说明/提示

约束条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • NN 为整数
  • SS 和 TT 均为长度为 NN 的小写英文字母字符串

样例解释 1

通过以下 4 次操作可将 SS 变为 TT:

  1. 选择 x=x= b, y=y= c,操作后 S=S= afcfda
  2. 选择 x=x= a, y=y= b,操作后 S=S= bfcfdb
  3. 选择 x=x= f, y=y= k,操作后 S=S= bkckdb
  4. 选择 x=x= d, y=y= b,操作后 S=S= bkckbb(与 TT 一致)

由于无法在 3 次或更少操作内完成,最小操作次数为 4。

样例解释 2

SS 与 TT 初始时已一致,无需任何操作。

样例解释 3

无论如何操作,都无法将 SS 变为 TT。

翻译由 DeepSeek R1 完成

输入解题思路,AI测评打分。不知道怎么写?

首页