首页 > 试题广场 >

字母交换

[编程题]字母交换
  • 热度指数：5192 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

【编码题】字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？



输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)


输出描述:
一个非负整数，表示操作之后，连续最长的相同字母数量。
示例1

输入

abcbaa 2

输出

2

说明

使2个字母a连续出现，至少需要3次操作。即把第1个位置上的a移动到第4个位置。
所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 17:59:21
题解 题目难度：中等 知识点：动态规划 分析： 设置一个大小为26*N的二维矩阵存放字母及字母在字符串中出现的位置，26行表示26个字母，N列表示对应字母出现的位置vector< vector<int> > vec(26); for(int i=0; i<str.s 展开全文
去ta的博客 赞 (17) 回复(4) 收起
头像 SoulRoar
发表于 2025-02-18 13:33:20
s, m = input().split() m = int(m) from collections import defaultdict positions = defaultdict(list) for idx, c in enumerate(s): positions[c].app 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2023-12-12 19:05:22
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; public class Main { public static void mai 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Artilleryyy
发表于 2024-09-25 11:46:29
def cnt(vec, m): # vec: 当前字母的所有位置列表 (vec存储了某一个字母出现在字符串中的位置) # m: 允许的最大交换次数 n = len(vec) # n 是这个字母在字符串中出现的次数 # 初始化一个二维dp数组，dp[i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 字符串 算法工程师 2018 字节跳动
上传者：小小
难度：
30条回答 12751浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字母交换

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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