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

本文主要是介绍LeetCode 2645. 构造有效字符串的最少插入数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

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();}
};

这篇关于LeetCode 2645. 构造有效字符串的最少插入数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---