Longest Happy String

Problem Description

A string s is called happy if it satisfies all of the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b', and at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

Examples

Constraints

• 0 ≤ a, b, c ≤ 100

Greedily Use the Most Available Character

At each step, add the most frequent remaining character, unless doing so would create three consecutive same characters. In that case, use the second-most frequent character instead.

If the most frequent character would create a triple (the last two characters already match it), try the second-most frequent. If neither can be added without creating a triple, stop.

The max-heap naturally gives you the most frequent character at each step.

Solution: Max-Heap Greedy

import java.util.*;

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        if (a > 0) heap.offer(new int[]{a, 'a'});
        if (b > 0) heap.offer(new int[]{b, 'b'});
        if (c > 0) heap.offer(new int[]{c, 'c'});

        StringBuilder result = new StringBuilder();

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int n = result.length();

            // if adding top would create 3 consecutive, try second
            if (n >= 2 && result.charAt(n - 1) == top[1] && result.charAt(n - 2) == top[1]) {
                if (heap.isEmpty()) break; // nowhere to go
                int[] second = heap.poll();
                result.append((char) second[1]);
                if (--second[0] > 0) heap.offer(second);
                heap.offer(top); // put top back
            } else {
                result.append((char) top[1]);
                if (--top[0] > 0) heap.offer(top);
            }
        }

        return result.toString();
    }
}

import heapq

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        heap = []
        for count, char in [(-a, 'a'), (-b, 'b'), (-c, 'c')]:
            if count < 0:
                heapq.heappush(heap, (count, char))

        result = []

        while heap:
            count, char = heapq.heappop(heap)
            n = len(result)

            # if adding would create 3 consecutive, try second
            if n >= 2 and result[-1] == char and result[-2] == char:
                if not heap:
                    break  # nowhere to go
                count2, char2 = heapq.heappop(heap)
                result.append(char2)
                if count2 + 1 < 0:
                    heapq.heappush(heap, (count2 + 1, char2))
                heapq.heappush(heap, (count, char))  # put top back
            else:
                result.append(char)
                if count + 1 < 0:
                    heapq.heappush(heap, (count + 1, char))

        return ''.join(result)

#include <string>
#include <queue>
#include <vector>

class Solution {
public:
    std::string longestDiverseString(int a, int b, int c) {
        std::priority_queue<std::pair<int,char>> heap;
        if (a) heap.push({a, 'a'});
        if (b) heap.push({b, 'b'});
        if (c) heap.push({c, 'c'});

        std::string result;

        while (!heap.empty()) {
            auto [cnt, ch] = heap.top(); heap.pop();
            int n = result.size();

            if (n >= 2 && result[n-1] == ch && result[n-2] == ch) {
                if (heap.empty()) break;
                auto [cnt2, ch2] = heap.top(); heap.pop();
                result += ch2;
                if (cnt2 - 1 > 0) heap.push({cnt2 - 1, ch2});
                heap.push({cnt, ch}); // put top back
            } else {
                result += ch;
                if (cnt - 1 > 0) heap.push({cnt - 1, ch});
            }
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O((a + b + c) * log 3) = O(a + b + c). The heap has at most 3 elements, so heap operations are O(1). The result length is at most a + b + c.
• Space Complexity: O(1). The heap has constant size.

Where it breaks: if a = 100, b = 0, c = 0, the maximum happy string is "aa" (not 100 as). The loop terminates when the top character would create a triple and there’s no second character to fall back to.

Common Mistakes

• Not putting the top character back after using the second. If you use the second character, the top character still has remaining count and needs to go back in the heap.
• Checking only the last character instead of the last two. You need two consecutive same characters to trigger the fallback, not just one.

Frequently Asked Questions

Is the output always maximal? Yes. The greedy choice (use the most frequent available) is optimal: using a less frequent character when the most frequent is available only delays usage and can’t increase the total length.

How is this different from Reorganize String? Reorganize String has a hard constraint (no two adjacent same) and works over arbitrary letters. Longest Happy String allows up to two consecutive same characters and works over exactly three letter types with given counts.

← All Problems