首页 > 试题广场 >

字符串替换

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

给定一个仅由小写字母x和y组成且长度不超过105的字符串，每次可以将字符串中的一个子串xy替换成字符串yyx，那么至少要替换多少次才能让字符串中不存在子串xy？


输入描述:
输入给定的字符串。


输出描述:
输出最少替换次数对109+7取模后的结果。
示例1

输入

xxy

输出

3
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-27 02:05:20
解题思路 题目要求计算将字符串中的子串"xy"替换成"yx"，最少需要多少次操作才能让字符串中不存在"xy"。 关键发现： 每次替换"xy"为"yx"，相当于将x向右移动一位 对于每个x，需要统计其 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-18 14:06:46
题目链接 字符串替换 题目描述 给定一个仅由小写字母 x 和 y 组成的字符串。 一次操作可以将字符串中的一个子串 xy 替换为 yyx。 求至少需要多少次替换，才能让字符串中不存在子串 xy？结果需要对 10^9 + 7 取模。 解题思路 (修正版) 这是一个巧妙的递推问题。关键在于选择正确的遍历 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 动态规划 度小满 字符串 模拟 2019 Java工程师
来自：度小满2019秋招研发岗试卷
上传者：小小
难度：
8条回答 10836浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串替换

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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