构造有效字符串的最少插入数
题目要求
解题思路
考虑abc的个数
假设答案有n个"abc"组成，那么需要插入的字符个数为 3 ∗ n − l e n ( s ) 3*n - len(s) 3∗n−len(s)。
对于相邻的两个字符x和y（x在y左侧）：文章来源：https://www.toymoban.com/news/detail-799002.html
- 如果 x < y x<y x<y，那么x和y可以在同一个"abc"内，否则一定不在；
- 如果 x ≥ y x\ge y x≥y，那么x和y一定不可以在同一个"abc"内，
所以， n n n就是 x ≥ y x\ge y x≥y 的次数加1文章来源地址https://www.toymoban.com/news/detail-799002.html
代码
class Solution:
def addMinimum(self, s: str) -> int:
ans = ord(s[0]) - ord(s[-1]) + 2
for x, y in pairwise(map(ord, s)):
ans += (y - x + 2) % 3
return ans
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)，其中 n n n为word的长度
- 空间复杂度： O ( 1 ) O(1) O(1)
到了这里，关于算法第十七天-构造有效字符串的最少插入数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[Go版]算法通关村第十二关黄金——字符串冲刺题](https://imgs.yssmx.com/Uploads/2024/02/657183-1.png)
