首页 > 试题广场 >

多多的字符变换

[编程题]多多的字符变换
  • 热度指数：5669 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

多多君最近在研究字符串之间的变换，可以对字符串进行若干次变换操作:

  1. 交换任意两个相邻的字符，代价为0。
  2. 将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。
现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。


输入描述:
共三行，第一行，一个整数N，表示字符串的长度。
（1 <= N <= 2,000）
接下来两行，每行分别是一个字符串，表示字符串X和Y。
（字符串中仅包含小写字母）


输出描述:
共一行，一个整数，表示将X和Y变换成一样的字符串需要的最小的总代价。
示例1

输入

4
abca
abcd

输出

3

说明

其中一种代价最小的变换方案：
都修改为abcd，那么将第一个字符串X最后一个字符a修改为d，代价为|a - d| = 3。
示例2

输入

4
baaa
aabb

输出

1

说明

其中一种代价最小的变换方案：
首先将第一个字符串通过交换相邻的字符：baaa -> abaa -> aaba，代价为0。
然后将第二个字符串修改最后一个字符b：|b - a| = 1。
两个字符都修改为aaba，所以最小的总代价为1。
示例3

输入

3
abc
xyz

输出

69
算法知识视频讲解
添加回答
Python
Bayes305头像 Bayes305
Python3 
import string
n=int(input())
s1=input()
s2=input()
d1={}
d2={}
for i in range(n):
    d1[s1[i]]=d1.get(s1[i],0)+1
    d2[s2[i]]=d2.get(s2[i],0)+1
total=0
rest=0
for letter in string.ascii_lowercase:
    rest+=d1.get(letter,0)-d2.get(letter,0)
    total+=abs(rest)
print(total)



发表于 2021-10-29 07:46:07 回复(0)
Python
牛客977766463号头像 牛客977766463号
n=int(input().strip())
a=sorted(input().strip())
b=sorted(input().strip())
dai=0
for i in range(n):
    if ord(a[i])>=ord(b[i]):
        dai+=ord(a[i])-ord(b[i])
    else:
        dai+=ord(b[i])-ord(a[i])
print(dai)
发表于 2021-05-10 22:37:28 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 拼多多 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
2条回答 7461浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号