Question

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

English Version

题目描述

给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。

如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。

 

示例 1：

输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。

示例 2：

输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。

示例 3：

输入：word = "abc"
输出：0
解释：word 已经是有效字符串，不需要进行修改。 

 

提示：

• 1 <= word.length <= 50
• word 仅由字母 "a"、"b" 和 "c" 组成。

解法

方法一：贪心 + 双指针

我们定义字符串 $s$ 为 "abc"，用指针 $i$ 和 $j$ 分别指向 $s$ 和 $word$。

如果 $word[j] \neq s[i]$，则需要插入 $s[i]$，我们将答案加 $1$；否则，说明 $word[j]$ 可以与 $s[i]$ 匹配，我们将 $j$ 右移一位。

然后，我们将 $i$ 右移一位，即 $i = (i + 1) \bmod 3$。继续上述操作，直到 $j$ 到达字符串 $word$ 的末尾。

最后，我们判断 $word$ 的最后一个字符是否为 'b' 或者 'a'，如果是，则需要插入 'c' 或者 'bc'，我们将答案加 $1$ 或者 $2$ 后返回即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $word$ 的长度。空间复杂度 $O(1)$。

class Solution:
  def addMinimum(self, word: str) -> int:
    s = 'abc'
    ans, n = 0, len(word)
    i = j = 0
    while j < n:
      if word[j] != s[i]:
        ans += 1
      else:
        j += 1
      i = (i + 1) % 3
    if word[-1] != 'c':
      ans += 1 if word[-1] == 'b' else 2
    return ans

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;
  }
}

class Solution {
public:
  int addMinimum(string word) {
    string s = "abc";
    int ans = 0, n = word.size();
    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
      if (word[j] != s[i]) {
        ++ans;
      } else {
        ++j;
      }
    }
    if (word[n - 1] != 'c') {
      ans += word[n - 1] == 'b' ? 1 : 2;
    }
    return ans;
  }
};

func addMinimum(word string) (ans int) {
  s := "abc"
  n := len(word)
  for i, j := 0, 0; j < n; i = (i + 1) % 3 {
    if word[j] != s[i] {
      ans++
    } else {
      j++
    }
  }
  if word[n-1] == 'b' {
    ans++
  } else if word[n-1] == 'a' {
    ans += 2
  }
  return
}

function addMinimum(word: string): number {
  const s: string = 'abc';
  let ans: number = 0;
  const n: number = word.length;
  for (let i = 0, j = 0; j < n; i = (i + 1) % 3) {
    if (word[j] !== s[i]) {
      ++ans;
    } else {
      ++j;
    }
  }
  if (word[n - 1] === 'b') {
    ++ans;
  } else if (word[n - 1] === 'a') {
    ans += 2;
  }
  return ans;
}