STACK

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

这题模拟栈即可，不需要真的用，因为一直访问的都是栈顶元素，所以维护一个栈顶指针即可。

维护下一个需要使用到的元素。例如上一个是a，那么下一个就是b。如果上一个是c，那么下一个是a。取余即可。

如果当前元素位于这个应有的元素后方，那么需要补齐中间的；如果在前方，说明上一轮abc还有缺，需要补上；如果正好就是这个应有元素，那么看下一个字符即可。

时间O(n)空间O(1)

class Solution {
    static int mod = 3;
    public int addMinimum(String word) {
        char[] ch = word.toCharArray();
        int top=0,dis;
        int cnt = 0;
        int index = 0;
        while(index<ch.length){
            char c = ch[index];
            dis = c-'a';
            if(dis==top){
                top = (top+1)%mod;
                index++;
            }else{
                if(dis>top){
                    cnt += dis-top;
                }else{
                    cnt += mod+dis-top;
                }
                top = dis;
            }
        }
        if(top!=0){
            cnt += mod - top;
        }
        return cnt;
    }
}