LC.P2645[构造有效字符串的最少插入数]

方法一：贪心+双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int addMinimum(String word) {
        String s = "abc";
        int ans = 0, n = word.length();
        for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
            if (word.charAt(j) != s.charAt(i)) {
                ++ans;
            } else {
                ++j;
            }
        }
        if (word.charAt(n - 1) != 'c') {
            ans += word.charAt(n - 1) == 'b' ? 1 : 2;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$