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

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

思路

1. 决定开头的差距；
2. 决定中间的补足
3. 决定末尾的差距；

解题方法

• 开头的位置对于a不做处理，b则做出加一的处理，c则是加二的处理方法；
• 中间的位置对于当前位置是a，如果下一个位置是b，不做处理，如果是c则是加一，a则是加2；
• 同理可得b对于a+1，b+2，c对于b+1，c+2.
• 综合上面两点，将加一和加二的情况进行分类处理；
  末尾c不处理，b+1，a+2

复杂度

时间复杂度： $O(n)$

添加空间复杂度 $O(1)$

Code

class Solution {
public:
    int addMinimum(string word) {
        int len=word.size();
        int aMinimum=0;
        aMinimum+=abs('a'-word[0]);
        aMinimum+='c'-word[len-1];
        for(int i =1;i<len;++i){
            if(word[i-1]-word[i]==-2||word[i-1]-word[i]==1){
                aMinimum+=1;
            }
            if(word[i-1]==word[i]){
                aMinimum+=2;
            }
        }
        return aMinimum;
    }
};