构造最长的新字符串

You are given three integers x, y, and z.

You have x strings equal to "AA", y strings equal to "BB", and z strings equal to "AB". You want to choose some (possibly all or none) of these strings and concatenate them in some order to form a new string. This new string must not contain "AAA" or "BBB" as a substring.

Return the maximum possible length of the new string.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: x = 2, y = 5, z = 1
Output: 12
Explanation: We can concactenate the strings "BB", "AA", "BB", "AA", "BB", and "AB" in that order. Then, our new string is "BBAABBAABBAB". 
That string has length 12, and we can show that it is impossible to construct a string of longer length.

Example 2:

Input: x = 3, y = 2, z = 2
Output: 14
Explanation: We can concactenate the strings "AB", "AB", "AA", "BB", "AA", "BB", and "AA" in that order. Then, our new string is "ABABAABBAABBAA". 
That string has length 14, and we can show that it is impossible to construct a string of longer length.

 

Constraints:

• 1 <= x, y, z <= 50

/*
 * 思路：
 * 使用Java Stream API来实现同样的贪心算法。这里主要是通过Stream来简化循环逻辑。
 */
import java.util.stream.Stream;

public class Solution {
    public int getMaxLength(int x, int y, int z) {
        int[] counts = {x, y, z};
        return Stream.generate(() -> {
            int maxIndex = -1;
            int maxCount = -1;
            for (int i = 0; i < 3; i++) {
                if (counts[i] > maxCount) {
                    maxCount = counts[i];
                    maxIndex = i;
                }
            }
            if (maxIndex == -1) return 0;
            counts[maxIndex] -= 2;
            return 2;
        })
        .limit((x + y + z) / 2)
        .mapToInt(Integer::intValue)
        .sum();
    }
}

这个题解首先利用了贪心策略来最大化生成字符串的长度。主要思路是：1. 尽可能多地使用'AB'字符串，因为它可以在不违背规则的情况下插入在'AA'和'BB'之间。2. 当'AB'用尽后，根据'AA'和'BB'的数量，交替放置'AA'和'BB'直到其中一种用完。3. 如果'AA'和'BB'数量不相等，那么在数量较多的那种字符后再添加一个相同的字符，但不能超过两个连续的相同字符。计算方法中，min(x, y) * 2计算了可以安全交替放置的'AA'和'BB'的总数量，(x != y)用于检查'AA'和'BB'的数量是否不相同，如果不相同，那么可以额外再放置一个字符，z * 2计算了可以由'AB'提供的字符数。

O(1)

O(1)