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

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

解题思路

解决此问题需要确定如何以最小的插入次数构造一个有效的字符串。首先，我们需要确定开头的差距，然后决定中间的补足，最后决定末尾的差距。

解决方法

在确定开头的差距时，我们可以对字符a不进行任何处理，b增加1，c增加2。

对于中间位置的补足，如果当前位置是a，且下一个位置是b，则不进行任何处理；如果是c则增加1；如果是a则增加2。同理，如果当前位置是b，且下一个位置是a，+1，b，+2；如果是c，则b，+1，c，+2。

对于末尾的差距，c不处理，b增加1，a增加2。

复杂度分析

时间复杂度：$O(n)$，其中n是字符串的长度。这是因为我们需要遍历整个字符串来确定每个位置的最小插入次数。

空间复杂度：$O(1)$。这是因为我们只使用了几个变量来存储中间结果，这些变量的大小是常数，所以空间复杂度为O(1)。

代码实现

class Solution {
public:int addMinimum(string word) {int len = word.size();int aMinimum = 0;aMinimum += abs('a' - word[0]); // 开头a不处理aMinimum += 'c' - word[len - 1]; // 末尾c不处理for (int i = 1; i < len; ++i) { // 遍历中间字符if (word[i - 1] - word[i] == -2 || word[i - 1] - word[i] == 1) { // 下一个字符与当前字符相差-2或1，不处理aMinimum += 1;} else if (word[i - 1] == word[i]) { // 下一个字符与当前字符相同，需要增加2或者1aMinimum += 2;} else { // 下一个字符与当前字符不同且相差大于1，需要增加1aMinimum += 1;}}return aMinimum; // 返回最小插入次数}
};