Java 字符串插入 'a' 最大数量 - 避免连续三个 'a'

以下是 Java 实现代码：

public class Solution {
    public int maxA(String S) {
        int n = S.length();
        if (n < 2) return 0;
        if (S.contains('aaa')) return -1;

        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = S.charAt(0) == 'a' ? 1 : 0;

        for (int i = 2; i <= n; i++) {
            if (S.charAt(i-1) == 'a') {
                if (S.charAt(i-2) == 'a') {
                    if (i >= 3) {
                        dp[i] = Math.max(dp[i-1], dp[i-3] + 1);
                    } else {
                        dp[i] = dp[i-1];
                    }
                } else {
                    dp[i] = dp[i-1] + 1;
                }
            } else {
                dp[i] = dp[i-1];
            }
        }

        return dp[n];
    }
}

思路解析：

本题可以使用动态规划来解决。令 dp[i] 表示插入前 i 个字符时最多可以插入多少个字母 'a'。对于第 i 个字符，有以下三种情况：

1. 如果 S[i] = 'a'，那么有两种情况：

   1. 如果 S[i-1] = 'a'，那么第 i 个字母不能插入。此时需要考虑前面两个字符是否是 'aa'。如果是，则不能在前面插入 'a'，否则可以在前面插入 'a'。
   2. 如果 S[i-1] != 'a'，那么第 i 个字母可以插入。此时 dp[i] = dp[i-1] + 1。

2. 如果 S[i] != 'a'，那么第 i 个字母不能插入。此时 dp[i] = dp[i-1]。

根据上述状态转移方程，我们可以得到动态规划的递推式。最终的答案即为 dp[n]，其中 n 是字符串 S 的长度。

需要注意的是，如果字符串 S 中包含子字符串 'aaa'，那么无论如何都无法插入字母 'a'，此时返回 -1。此外，初始状态 dp[0] = 0，dp[1] = 1（如果 S[0] = 'a'）。