Medium

题目描述

给定两个整数 a 和 b，返回任意一个满足下列条件的字符串 s：

  • s 的长度为 a + b，且正好包含 a 个 'a' 字母和 b 个 'b' 字母
  • 子字符串 'aaa' 不出现在 s 中
  • 子字符串 'bbb' 不出现在 s 中

示例 1：

输入：a = 1, b = 2
输出："abb"
解释："abb"、"bab" 和 "bba" 都是正确答案。

示例 2：

输入：a = 4, b = 1
输出："aabaa"

提示：

  • 0 <= a, b <= 100
  • 对于给定的 a 和 b，保证存在满足要求的 s

解题思路

这是一道贪心算法题目，核心思想是始终优先放置数量较多的字符，同时避免连续三个相同字符。

解题思路：

  1. 贪心策略：总是优先放置剩余数量更多的字符，这样可以最大化利用字符，避免某个字符过多导致无解。

  2. 放置规则：

    • 如果某个字符的剩余数量比另一个字符多2个或以上，则连续放置2个该字符
    • 否则只放置1个该字符
    • 然后切换到另一个字符

  3. 具体实现：

    • 维护当前剩余的a和b的数量
    • 比较a和b的大小，优先处理数量多的字符
    • 如果当前字符比另一个字符多很多（差值≥2），则放置2个当前字符
    • 否则放置1个当前字符
    • 交替进行直到所有字符用完

这种贪心策略能够保证不会出现连续三个相同字符的情况，因为我们最多连续放置2个相同字符，然后就会切换到另一个字符。

代码实现

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string result = "";
        
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a >= b + 2) {
                    result += "aa";
                    a -= 2;
                } else {
                    result += "a";
                    a--;
                }
                if (b > 0) {
                    result += "b";
                    b--;
                }
            } else {
                if (b >= a + 2) {
                    result += "bb";
                    b -= 2;
                } else {
                    result += "b";
                    b--;
                }
                if (a > 0) {
                    result += "a";
                    a--;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        result = []
        
        while a > 0 or b > 0:
            if a > b:
                if a >= b + 2:
                    result.append("aa")
                    a -= 2
                else:
                    result.append("a")
                    a -= 1
                if b > 0:
                    result.append("b")
                    b -= 1
            else:
                if b >= a + 2:
                    result.append("bb")
                    b -= 2
                else:
                    result.append("b")
                    b -= 1
                if a > 0:
                    result.append("a")
                    a -= 1
        
        return "".join(result)

public class Solution {
    public string StrWithout3a3b(int a, int b) {
        StringBuilder result = new StringBuilder();
        
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a >= b + 2) {
                    result.Append("aa");
                    a -= 2;
                } else {
                    result.Append("a");
                    a--;
                }
                if (b > 0) {
                    result.Append("b");
                    b--;
                }
            } else {
                if (b >= a + 2) {
                    result.Append("bb");
                    b -= 2;
                } else {
                    result.Append("b");
                    b--;
                }
                if (a > 0) {
                    result.Append("a");
                    a--;
                }
            }
        }
        
        return result.ToString();
    }
}

var strWithout3a3b = function(a, b) {
    let result = "";
    
    while (a > 0 || b > 0) {
        if (a > b) {
            if (a >= b + 2) {
                result += "aa";
                a -= 2;
            } else {
                result += "a";
                a--;
            }
            if (b > 0) {
                result += "b";
                b--;
            }
        } else {
            if (b >= a + 2) {
                result += "bb";
                b -= 2;
            } else {
                result += "b";
                b--;
            }
            if (a > 0) {
                result += "a";
                a--;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(a + b)需要遍历处理所有a+b个字符
空间复杂度O(1)除了结果字符串外，只使用常数额外空间