Medium

题目描述

如果字符串满足以下条件，则称为快乐字符串：

  • 字符串只包含字母 ‘a’、‘b’ 和 ‘c’
  • 字符串不包含任何 “aaa”、“bbb” 或 “ccc” 作为子字符串
  • 字符串包含最多 a 个字母 ‘a’
  • 字符串包含最多 b 个字母 ‘b’
  • 字符串包含最多 c 个字母 ‘c’

给定三个整数 a、b 和 c，返回最长的快乐字符串。如果有多个最长的快乐字符串，返回其中任意一个。如果不存在这样的字符串，返回空字符串 “"。

子字符串是字符串中字符的连续序列。

示例 1：

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

示例 2：

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

约束条件：

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

解题思路

这道题需要用贪心策略解决。核心思想是：总是优先使用数量最多的字符，但要避免连续三个相同字符。

解题思路：

  1. 优先队列策略：使用最大堆维护三个字符及其剩余数量，每次取出数量最多的字符
  2. 贪心选择：
    • 如果当前结果串末尾没有连续两个相同字符，直接添加数量最多的字符
    • 如果末尾已有两个相同字符，则必须选择数量次多的字符
  3. 添加策略：
    • 当某个字符数量明显超过其他字符时，可以连续添加两个该字符以加速消耗
    • 否则每次只添加一个字符

关键点：

  • 通过优先队列动态维护字符优先级
  • 合理处理连续字符限制
  • 在满足约束的前提下尽可能构造最长字符串

这种贪心策略能保证在每一步都做出局部最优选择，从而得到全局最优解。

代码实现

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int, char>> pq;
        if (a > 0) pq.push({a, 'a'});
        if (b > 0) pq.push({b, 'b'});
        if (c > 0) pq.push({c, 'c'});
        
        string result = "";
        
        while (!pq.empty()) {
            auto first = pq.top(); pq.pop();
            
            // 如果结果串末尾已有两个相同字符，不能再添加该字符
            if (result.length() >= 2 && result[result.length()-1] == first.second 
                && result[result.length()-2] == first.second) {
                if (pq.empty()) break;
                
                auto second = pq.top(); pq.pop();
                result += second.second;
                if (second.first - 1 > 0) {
                    pq.push({second.first - 1, second.second});
                }
                pq.push(first);
            } else {
                // 可以添加该字符
                int count = min(2, first.first);
                // 如果该字符数量远超其他字符，添加两个
                if (first.first >= 2 && !pq.empty() && first.first > pq.top().first) {
                    count = 2;
                } else {
                    count = 1;
                }
                
                for (int i = 0; i < count; i++) {
                    result += first.second;
                }
                
                if (first.first - count > 0) {
                    pq.push({first.first - count, first.second});
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        import heapq
        
        # 使用最大堆（Python中用负数实现）
        heap = []
        if a > 0:
            heapq.heappush(heap, (-a, 'a'))
        if b > 0:
            heapq.heappush(heap, (-b, 'b'))
        if c > 0:
            heapq.heappush(heap, (-c, 'c'))
        
        result = []
        
        while heap:
            first = heapq.heappop(heap)
            
            # 如果结果串末尾已有两个相同字符，不能再添加该字符
            if len(result) >= 2 and result[-1] == first[1] and result[-2] == first[1]:
                if not heap:
                    break
                
                second = heapq.heappop(heap)
                result.append(second[1])
                if second[0] < -1:
                    heapq.heappush(heap, (second[0] + 1, second[1]))
                heapq.heappush(heap, first)
            else:
                # 可以添加该字符
                count = min(2, -first[0])
                # 如果该字符数量远超其他字符，添加两个
                if -first[0] >= 2 and heap and -first[0] > -heap[0][0]:
                    count = 2
                else:
                    count = 1
                
                for _ in range(count):
                    result.append(first[1])
                
                if first[0] + count < 0:
                    heapq.heappush(heap, (first[0] + count, first[1]))
        
        return ''.join(result)

public class Solution {
    public string LongestDiverseString(int a, int b, int c) {
        var pq = new PriorityQueue<(int count, char ch), int>(
            Comparer<int>.Create((x, y) => y.CompareTo(x)));
        
        if (a > 0) pq.Enqueue((a, 'a'), a);
        if (b > 0) pq.Enqueue((b, 'b'), b);
        if (c > 0) pq.Enqueue((c, 'c'), c);
        
        var result = new StringBuilder();
        
        while (pq.Count > 0) {
            var first = pq.Dequeue();
            
            // 如果结果串末尾已有两个相同字符，不能再添加该字符
            if (result.Length >= 2 && result[result.Length - 1] == first.ch 
                && result[result.Length - 2] == first.ch) {
                if (pq.Count == 0) break;
                
                var second = pq.Dequeue();
                result.Append(second.ch);
                if (second.count - 1 > 0) {
                    pq.Enqueue((second.count - 1, second.ch), second.count - 1);
                }
                pq.Enqueue(first, first.count);
            } else {
                // 可以添加该字符
                int count = Math.Min(2, first.count);
                // 如果该字符数量远超其他字符，添加两个
                if (first.count >= 2 && pq.Count > 0 && first.count > pq.Peek().count) {
                    count = 2;
                } else {
                    count = 1;
                }
                
                for (int i = 0; i < count; i++) {
                    result.Append(first.ch);
                }
                
                if (first.count - count > 0) {
                    pq.Enqueue((first.count - count, first.ch), first.count - count);
                }
            }
        }
        
        return result.ToString();
    }
}

var longestDiverseString = function(a, b, c) {
    // 使用数组模拟最大堆
    const heap = [];
    if (a > 0) heap.push([a, 'a']);
    if (b > 0) heap.push([b, 'b']);
    if (c > 0) heap.push([c, 'c']);
    
    // 堆排序函数
    const heapify = () => {
        heap.sort((x, y) => y[0] - x[0]);
    };
    
    let result = '';
    
    while (heap.length > 0) {
        heapify();
        const first = heap.shift();
        
        // 如果结果串末尾已有两个相同字符，不能再添加该字符
        if (result.length >= 2 && result[result.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log 3) = O(n)n为a+b+c的总和，每次操作需要O(log 3)的堆操作
空间复杂度O(1)堆最多存储3个元素，结果字符串不计入额外空间

相关题目