【Lintcode】1340. add character

题目地址：

https://www.lintcode.com/problem/add-character/description

给定一个字符串，如果其不包含子串"aaa"，称其合法。允许在这个字符串的任意位置插入字符'a'，如果要保持字符串合法，最多可以加多少个'a'。题目保证初始字符串合法。

可以遍历两次，第一次数一下连续的a的位置，能插入多少个，然后第二次数一下两个非a的地方能插入多少个，累加起来即可。代码如下：

public class Solution {
    /*** @param str:* @return: the max sum you can add*/public int addCharacter(String str) {
    // Write your code here.if (str == null || str.isEmpty()) {
    return 2;}int res = 0;for (int i = 0, j; i < str.length(); i++) {
    if (str.charAt(i) == 'a') {
    j = i;while (j < str.length() && str.charAt(j) == 'a') {
    j++;}res += 2 - (j - i);i = j;}}// 首尾如果能插入的话就累加上去if (str.charAt(0) != 'a') {
    res += 2;}if (str.charAt(str.length() - 1) != 'a') {
    res += 2;}for (int i = 0; i < str.length() - 1; i++) {
    if (str.charAt(i) != 'a' && str.charAt(i + 1) != 'a') {
    res += 2;}}return res;}
}

时间复杂度$O(n)$，空间$O(1)$。