首页 > 试题广场 >

字符串替换

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

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


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


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

输入

xxy

输出

3
头像 bandiaoz
发表于 2024-12-27 02:05:20
解题思路 题目要求计算将字符串中的子串"xy"替换成"yx",最少需要多少次操作才能让字符串中不存在"xy"。 关键发现: 每次替换"xy"为"yx",相当于将x向右移动一位 对于每个x,需要统计其 展开全文