首页 > 试题广场 >

字符串替换

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

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


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


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

输入

xxy

输出

3
算法知识视频讲解
添加回答
Python
LitterF头像 LitterF
暴力模拟法从后往前算一下就行了，秒A的题
从后往前数，是x就挪到y的后面，然后挪的时候xy变成了yyx，y的数量翻了一倍，xyy就变成yyyyx。 
s = input()
cur_y = 0
res = 0
mo = 10**9+7
for i in s[::-1]:
    if i=='y':
        cur_y+=1
    if i=='x':
        res+=cur_y
        cur_y*=2
print(res%mo)


发表于 2019-10-28 23:04:25 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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