LEETCODE 1405. Longest Happy String 解题思路分析

题目大意：

最长快乐字符串

如果字符串中不含有任何 ‘aaa’，’bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

• s 是一个尽可能长的快乐字符串。
• s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
• s 中只含有 ‘a’、’b’ 、’c’ 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 ""。

示例 1：

输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。

示例 2：

输入：a = 2, b = 2, c = 1
输出："aabbc"

示例 3：

输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。

提示：

• 0 <= a, b, c <= 100
• a + b + c > 0

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1405

解题思路分析：

本题的最优方案是采用贪心算法，算法核心如下：

1. 找出a，b，c中个数最多的那个字母，选择2个加入到返回结果（如果不足2个时，将剩余的个数全部加入）。
2. 重复第一步，如果当前个数最多的字母与上一次相同，那么选择一个个数次多的字母加入返回结果。反之选择2个个数最多的字母加入返回结果（如果不足2个时，将剩余的个数全部加入）。
3. 直到三中字母的个数都为0时，结束循环。

实现代码：

public String longestDiverseString(int a, int b, int c) {
    StringBuilder sb = new StringBuilder();
    char lastMax='-';
    while(a>0||b>0||c>0){
        if(a>=b&&a>=c){ // 当字母a的个数最多时
            if(lastMax != 'a'){ // 上一次个数最多的字母不是a
                sb.append("a"); // 添加一个a至返回结果
                if(a>1) sb.append("a"); // 如果a还有剩余，再添加一个
                a-=2; // a的个数减去2
                lastMax='a'; // 更新上一个个数最多的字母是a
            }else{ // 如果上一次个数最多的字母也是a
                if(b>c){ // 次多的字母是b
                    sb.append("b"); // 添加一个b
                    b--; // b的个数减一
                    lastMax='b'; // 更新上一个个数最多的字母是a
                }else if(c>0){ // 次多的字母是c
                    sb.append("c"); // 添加一个c
                    c--; // c的个数减一
                    lastMax='c'; // 更新上一个个数最多的字母是c
                }else break;
            }
        }else if(b>=a&&b>=c){
            if(lastMax != 'b'){
                sb.append("b");
                if(b>1) sb.append("b");
                b-=2;
                lastMax='b';
            }else{
                if(a>c){
                    sb.append("a");
                    a--;
                    lastMax='a';
                }else if(c>0){
                    sb.append("c");
                    c--;
                    lastMax='c';
                }else break;
            }
        }else if(c>=a&&c>=b){
            if(lastMax != 'c'){
                sb.append("c");
                if(c>1) sb.append("c");
                c-=2;
                lastMax='c';
            }else{
                if(a>b){
                    sb.append("a");
                    a--;
                    lastMax='a';
                }else if(b>0){
                    sb.append("b");
                    b--;
                    lastMax='b';
                }else break;
            }
        }
    }
    return sb.toString();
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Happy String.

Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Longest Happy String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1405-longest-happy-string-解题思路分析/