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

发布时间:2024年01月11日

一、题目

1、题目描述

LeetCode 给你一个字符串 word ,你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次,返回使 word 有效 需要插入的最少字母数。如果2645. 构造有效字符串的最少插入数

2、接口描述

?
class Solution {
public:
    int addMinimum(string word) {
        
    }
};

3、原题链接

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


二、解题报告

1、思路分析

假如我们最终有cnt个“abc”,那么我们需要插入cnt - len(s)个字符

所以我们只需要计算出cnt即可

我们遍历字符串,如果当前字符小于前面字符,说明二者不在一个abc中,cnt+1

注意cnt初始为1

2、复杂度

时间复杂度: O(N) 空间复杂度:O(1)

3、代码详解

?
class Solution {
public:
    int addMinimum(string s) {
        int t = 1;
        for(int i = 1 , n = s.size() ; i < n ; i++)
            t += s[i - 1] >= s[i];
        return t * 3 - s.size();
    }
};

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135516111
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。