算法第十七天-构造有效字符串的最少插入数

发布时间：2024-01-13 10:29:47

构造有效字符串的最少插入数

题目要求

解题思路

考虑abc的个数

假设答案有n个"abc"组成，那么需要插入的字符个数为 3 ? n ? l e n ( s ) 3*n - len(s) 3?n?len(s)。

对于相邻的两个字符x和y（x在y左侧）：

  • 如果 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

代码


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)
文章来源:https://blog.csdn.net/weixin_43186779/article/details/135565707
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章