给你一个字符串 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 <= 50word 仅由字母 “a”、“b” 和 “c” 组成。这道题乍一看很简单，仔细一想又容易混乱，写出又臭又长的if-else嵌套代码，维护性很差。比如
class Solution:
def addMinimum(self, word: str) -> int:
ans = 0
word = "c" + word + "a"
n = len(word)
if n == 3:
return 2
# 分别考虑前后位置是否需要插入
for i in range(1, n-1):
ch = word[i]
if ch == "a":
if word[i+1] == "a":
ans += 2
elif word[i+1] == "c":
ans += 1
elif ch == "b":
if word[i+1] != "c":
ans += 1
if word[i-1] != "a":
ans += 1
elif ch == "c":
if word[i-1] == "c":
ans += 2
return ans
贪心地思考这个问题，如果我们发现相邻字符之间并不有效，即不属于"ab"，"bc"，"ca"中的任意一种，则必然要在这两个字符串之间进行字符的插入。
考虑原字符串中相邻的两个字符word[i+1]和word[i]，并同时考虑它们的ASCII码值差ord(word[i+1])-ord(word[i])。一共有三种可能的情况：
"aa","bb","cc"：需要在中间补2个字符，码值差 mod 3 后为0"ba","cb","ac"：需要在中间补1个字符，码值差 mod 3 后为2"ab","bc","ca"：需要在中间补0个字符，码值差 mod 3 后为1为了使得码值差 mode 3 后得到的结果(0,2,1)可以映射上所需补充的字符数(2,1,0)，可以构建出答案增量为(ord(word[i+1]) - ord(word[i]) + 2) % 3
此外，发现上述过程由于要考虑相邻的两个字符，对第一个字符和最后一个字符需要额外讨论。为了避免这种分类讨论，一个小技巧是在word的最前面补一个"c"，在word的最后面补一个"a"，则可以令边界处首尾两个字符也遵循上述贪心过程。
# 贪心：O(N)
class Solution:
def addMinimum(self, word: str) -> int:
# 小技巧，在word最前面补一个"c"，最后面补一个"a"
# 这样可以使得边界处也遵循后面遍历的规律
word = "c" + word + "a"
ans = 0
# 贪心地考虑相邻的两个字符word[i+1]和word[i]，
# 并同时考虑ASCII码值差ord(word[i+1])-ord(word[i])
# 一共有三种可能的情况：
# "aa","bb","cc"：需要在中间补2个字符，码值差 mod 3 后为0
# "ba","cb","ac"：需要在中间补1个字符，码值差 mod 3 后为2
# "ab","bc","ca"：需要在中间补0个字符，码值差 mod 3 后为1
# 为了使得码值差模3后得到的结果(0,2,1)可以映射上所需补充的字符数(2,1,0)
# 可以构建出答案增量为 (ord(word[i+1]) - ord(word[i]) + 2) % 3
for i in range(0, len(word)-1):
ans += (ord(word[i+1]) - ord(word[i]) + 2) % 3
return ans
public class Solution {
public int addMinimum(String word) {
word = "c" + word + "a";
int ans = 0;
for (int i = 0; i < word.length() - 1; i++) {
ans += (word.charAt(i + 1) - word.charAt(i) + 2) % 3;
}
return ans;
}
}
class Solution {
public:
int addMinimum(string word) {
word = 'c' + word + 'a';
int ans = 0;
for (int i = 0; i < word.length() - 1; i++) {
ans += (word[i + 1] - word[i] + 2) % 3;
}
return ans;
}
};
时间复杂度：O(N)。
空间复杂度：O(1)。
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多