# 2645. Minimum Additions to Make Valid String
###### tags: `Leetcode` `Medium` `Math`
Link: https://leetcode.com/problems/minimum-additions-to-make-valid-string/description/
## 思路
### 思路一
分情况讨论 根据当前遍历到的字母和它前面的字母 判断他们两个中间要加多少个字符
最后还要考虑最后面要加上几个字符
### 思路二
参考[这里](https://leetcode.com/problems/minimum-additions-to-make-valid-string/solutions/3421831/java-c-python-easy-and-concise-with-explanation/)
Find out the minimum ```k``` where ```word``` is subsequence of ```"abc"``` repeated ```k``` times.

Since ```"abc"``` is increasing,
so we can split the original work into ```k``` strict increasing subarray.
## Code
### 思路一

class Solution:
    def addMinimum(self, word: str) -> int:
        ans = 0
        for i in range(len(word)):
            if word[i]=='a':
                if i-1>=0 and word[i-1]!='c':
                    ans += 1 if word[i-1]=='b' else 2
            elif word[i]=='b':
                if i-1<0: ans += 1
                elif word[i-1]!='a': ans += 1 if word[i-1]=='c' else 2
            else:
                if i-1<0: ans += 2
                elif word[i-1]!='b': ans += 1 if word[i-1]=='a' else 2
        if word[-1]!='c':
            ans += 1 if word[-1]=='b' else 2
        return ans

### 思路二

class Solution:
    def addMinimum(self, word: str) -> int:
        k = 0
        prev = 'z'
        for i in range(len(word)):
            if prev>=word[i]:
                k += 1
            prev = word[i]
        return k*3-len(word)