2645. Minimum Additions to Make Valid String

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int addMinimum(String word) {
        int ans = 0;

        ans += word.charAt(0) - 'a';
        for (int i = 0; i < word.length() - 1; i++) { // 遍历空隙，计算每个空隙需要插入几个字符
            ans += (word.charAt(i + 1) - word.charAt(i) - 1 + 3) % 3;
        }
        ans += 'c' - word.charAt(word.length() - 1);

        return ans;
    }
}

Math

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int addMinimum(String word) {
        int groupCount = 1;
        for (int i = 1; i < word.length(); i++) {
            if (word.charAt(i - 1) >= word.charAt(i)) {
                groupCount++;
            }
        }

        return 3 * groupCount - word.length();
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int addMinimum(String word) {
        int n = word.length();

        // 定义 dp[i] 为使 word[0, i - 1] 有效需要插入的最少字母数
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 2;
            if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {
                dp[i] = dp[i - 1] - 1;
            }
        }

        return dp[n];
    }
}

References

2645. Minimum Additions to Make Valid String