1405. Longest Happy String Solution - Greedy Heap

The problem

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

s only contains the letters 'a', 'b', and 'c'.
s does not contain any of "aaa", "bbb", or "ccc" as a substring.
s contains at most a occurrences of the letter 'a'.
s contains at most b occurrences of the letter 'b'.
s contains 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 "".

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

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

Approach overview

Problem Overview: Given counts of characters a, b, and c, build the longest possible string where no character appears three times consecutively. The result can use any combination of these letters, but sequences like "aaa", "bbb", or "ccc" are not allowed.

Approach 1: Greedy Approach with Priority Queue (Time: O(n log 3), Space: O(1))

The core idea is always picking the character with the highest remaining frequency while preventing three identical characters in a row. Store the counts of a, b, and c in a max heap (priority queue). Each step removes the most frequent character and appends it to the result unless the last two characters already match it. If that happens, take the second-most frequent character instead, append it, and push both entries back with updated counts. Because the heap size never exceeds three elements, heap operations are effectively constant. This greedy strategy works because delaying the most frequent character only when necessary preserves future flexibility. The algorithm runs in O(n log 3) time, which simplifies to O(n), and uses O(1) extra space aside from the output string.

This solution relies on a greedy decision process combined with a heap (priority queue) to always select the best available character. The string construction itself is straightforward iteration over the total character count.

Approach 2: Simulated Annealing Strategy (Time: ~O(n * iterations), Space: O(n))

A less common but interesting strategy treats the problem as an optimization task. Start with a candidate string built from all available characters and repeatedly perform small modifications, such as swapping characters or adjusting positions. Each modification is evaluated based on how many valid characters remain without forming forbidden triples. Using simulated annealing, the algorithm occasionally accepts worse states early in the process to escape local optima, then gradually becomes stricter as the temperature decreases.

This probabilistic search can eventually converge to a near‑optimal or optimal happy string. However, its runtime depends on the number of iterations and randomness, typically around O(n * k) where k is the number of annealing steps. It also requires O(n) space to maintain candidate strings. While educational for exploring optimization techniques on string problems, it is rarely used in interviews because deterministic greedy solutions are simpler and faster.

Recommended for interviews: The greedy priority queue approach is the expected solution. It demonstrates control over heap operations, careful handling of constraints, and the ability to enforce rules while maximizing length. Showing the brute reasoning first (always pick the largest count but avoid triples) and then implementing it with a heap signals strong algorithmic thinking.

Approach 1: Greedy Approach with Priority Queue

This approach utilizes a max heap (or priority queue) to always try to append the character with the highest remaining count without breaking the "happy" condition. Here’s the detailed plan:

Initialize a max heap to store pairs of (remaining count, character) for 'a', 'b', and 'c'. Only characters with a positive count are inserted into the heap to start.
Pick the character with the largest count from the heap (say it’s 'X'). If you already have two 'X's at the end of the answer string, you should not append 'X' again directly.
If 'X' can be used, decrement its remaining count and append it to the result.
If 'X' cannot be directly used (because you already have two 'X's), pick the second most abundant character from the heap and append it instead, then continue.
Adjust the count for the characters in the heap and re-adjust the heap structure if needed.

Once you process all characters when the heap is non-empty, the constructed string is your answer.

Python

from heapq import heappop, heappush

def longestDiverseString(a: int, b: int, c: int) -> str:
    max_heap = []
    if a > 0: heappush(max_heap, (-a, 'a'))
    if b > 0: heappush(max_heap, (-b, 'b'))
    if c > 0: heappush(max_heap, (-c, 'c'))
    
    result = []
    while max_heap:
        count1, char1 = heappop(max_heap)
        if len(result) >= 2 and result[-1] == result[-2] == char1:
            if not max_heap:
                break
            count2, char2 = heappop(max_heap)
            result.append(char2)
            count2 += 1
            if count2:
                heappush(max_heap, (count2, char2))
            heappush(max_heap, (count1, char1))
        else:
            result.append(char1)
            count1 += 1
            if count1:
                heappush(max_heap, (count1, char1))
    
    return ''.join(result)

Java

import java.util.PriorityQueue;

public class LongestHappyString {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((x, y) -> Integer.compare(y[0], x[0]));
        if (a > 0) maxHeap.offer(new int[]{a, 'a'});
        if (b > 0) maxHeap.offer(new int[]{b, 'b'});
        if (c > 0) maxHeap.offer(new int[]{c, 'c'});
        
        StringBuilder result = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            int[] first = maxHeap.poll();
            int count = first[0];
            char letter = (char) first[1];
            
            if (result.length() >= 2 && result.charAt(result.length() - 1) == letter && result.charAt(result.length() - 2) == letter) {
                if (maxHeap.isEmpty()) break;
                int[] second = maxHeap.poll();
                result.append((char) second[1]);
                if (--second[0] > 0) maxHeap.offer(second);
                maxHeap.offer(first);
            } else {
                result.append(letter);
                if (--count > 0) maxHeap.offer(new int[]{count, letter});
            }
        }
        return result.toString();
    }
}

C++

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

std::string longestDiverseString(int a, int b, int c) {
    std::priority_queue<std::pair<int, char>> maxHeap;
    if (a > 0) maxHeap.emplace(a, 'a');
    if (b > 0) maxHeap.emplace(b, 'b');
    if (c > 0) maxHeap.emplace(c, 'c');
    
    std::string result;
    while (!maxHeap.empty()) {
        auto [count1, char1] = maxHeap.top(); maxHeap.pop();
        if (result.size() > 1 && result.back() == char1 && result[result.size()-2] == char1) {
            if (maxHeap.empty()) break;
            auto [count2, char2] = maxHeap.top(); maxHeap.pop();
            result += char2;
            if (--count2) maxHeap.emplace(count2, char2);
            maxHeap.emplace(count1, char1);
        } else {
            result += char1;
            if (--count1) maxHeap.emplace(count1, char1);
        }
    }
    
    return result;
}

JavaScript

var longestDiverseString = function(a, b, c) {
    const maxHeap = [];
    if (a > 0) maxHeap.push([a, 'a']);
    if (b > 0) maxHeap.push([b, 'b']);
    if (c > 0) maxHeap.push([c, 'c']);
    
    const addQueue = (item) => {
        maxHeap.push(item);
        maxHeap.sort((x, y) => y[0] - x[0]);
    }
    
    let result = '';
    while (maxHeap.length) {
        const [count1, char1] = maxHeap.shift();
        if (result.length >= 2 && result[result.length - 1] === char1 && result[result.length - 2] === char1) {
            if (!maxHeap.length) break;
            const [count2, char2] = maxHeap.shift();
            result += char2;
            if (--count2 > 0) addQueue([count2, char2]);
            addQueue([count1, char1]);
        } else {
            result += char1;
            if (--count1 > 0) addQueue([count1, char1]);
        }
    }
    
    return result;
};

using System;
using System.Collections.Generic;

public class Solution {
    public string LongestDiverseString(int a, int b, int c) {
        PriorityQueue<(int count, char ch)> queue = new PriorityQueue<(int, char)>(Comparer<(int, char)>.Create((x, y) => y.count.CompareTo(x.count)));
        if (a > 0) queue.Enqueue((a, 'a'));
        if (b > 0) queue.Enqueue((b, 'b'));
        if (c > 0) queue.Enqueue((c, 'c'));

        var result = new System.Text.StringBuilder();
        while (queue.Count > 0) {
            var (count1, char1) = queue.Dequeue();
            if (result.Length >= 2 && result[^1] == char1 && result[^2] == char1) {
                if (queue.Count == 0) break;
                var (count2, char2) = queue.Dequeue();
                result.Append(char2);
                if (--count2 > 0) queue.Enqueue((count2, char2));
                queue.Enqueue((count1, char1));
            } else {
                result.Append(char1);
                if (--count1 > 0) queue.Enqueue((count1, char1));
            }
        }

        return result.ToString();
    }
}

The function longestDiverseString uses a max heap to store the characters and their counts as negative values (since Python’s heapq is a min-heap). We always take two checks before appending: If the same character was used twice consecutively before, we opt for the next available character (if any). After appending a character, if there are still instances of this character left, we push it back into the heap with the updated count. This ensures the resulting string is as long as possible and never violates the 'happy' conditions.

Complexity

Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3).

Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts).

Try this approach in the editor

Approach 2: Simulated Annealing Strategy

This strategy incorporates the concepts of simulated annealing where the decision of which character to append is softly randomized, guided by the need to form a balanced happy string using all the available characters maximally — performing a structured simulation of building the string dynamically and reevaluating choices iteratively.

Python

def simulate_happy_string(a, b, c, order):
    counts = { 'a': a, 'b': b, 'c': c }
    result = []
    
    for ch in order:
        if len(result) >= 2 and result[-1] == result[-2] == ch:
            for alt_ch in order:
                if alt_ch != ch and counts[alt_ch] > 0:
                    result.append(alt_ch)
                    counts[alt_ch] -= 1
                    break
        elif counts[ch] > 0:
            result.append(ch)
            counts[ch] -= 1
    
    return ''.join(result)

def simulated_annealing_longest_happy_string(a, b, c):
    orders = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
    best_result = ""

    for order in orders:
        candidate = simulate_happy_string(a, b, c, order)
        if len(candidate) > len(best_result):
            best_result = candidate
    
    return best_result

C++

#include <string>
#include <tuple>

std::string generateHappyString(int a, int b, int c, const std::string& pattern) {
    std::string result;
    int counts[3] = {a, b, c};
    char chars[3] = {'a', 'b', 'c'};
    for (char pat : pattern) {
        auto [count, idx] = std::make_tuple(0, -1);
        if (result.size() >= 2 && result.back() == pat && result[result.size() - 2] == pat) {
            for (int i = 0; i < 3; ++i) {
                if (counts[i] > count && chars[i] != pat) {
                    count = counts[i];
                    idx = i;
                }
            }
            if (idx == -1) return result;
            result += chars[idx];
            counts[idx]--;
        } else {
            for (int i = 0; i < 3; ++i) {
                if (counts[i] > count && chars[i] == pat) {
                    count = counts[i];
                    idx = i;
                }
            }
            if (idx != -1) {
                result += pat;
                counts[idx]--;
            }
        }
    }
    return result;
}

std::string simulatedAnnealingLongestHappyString(int a, int b, int c) {
    std::string patterns[6] = {"abc", "acb", "bac", "bca", "cab", "cba"};
    std::string best;
    for (const auto& pattern : patterns) {
        std::string candidate = generateHappyString(a, b, c, pattern);
        if (candidate.size() > best.size()) {
            best = candidate;
        }
    }
    return best;
}

The Python implementation offers a simulated exploration of possibilities by generating strings in various character ordering permutations, testing each and comparing efficiently to find the most successful configurations for balanced, happy strings.

Complexity

Time Complexity: O(k! * n) with 3! possible entry sequences to maximize successful length under constraints.

Space Complexity: O(1), minimal additional structures beyond temporary allocations.

Try this approach in the editor

Approach 3: Greedy + Priority Queue

The greedy strategy is to prioritize the selection of characters with the most remaining occurrences. By using a priority queue or sorting, we ensure that the character selected each time is the one with the most remaining occurrences (to avoid having three consecutive identical characters, in some cases, we need to select the character with the second most remaining occurrences).

TypeScript

function longestDiverseString(a: number, b: number, c: number): string {
    const pq = new PriorityQueue<number[]>((a, b) => b[1] - a[1]);

    if (a > 0) pq.enqueue(['a'.charCodeAt(0), a]);
    if (b > 0) pq.enqueue(['b'.charCodeAt(0), b]);
    if (c > 0) pq.enqueue(['c'.charCodeAt(0), c]);

    const sb: number[] = [];

    while (!pq.isEmpty()) {
        const cur = pq.dequeue();
        const n = sb.length;

        if (n >= 2 && sb[n - 1] === cur[0] && sb[n - 2] === cur[0]) {
            if (pq.isEmpty()) break;

            const next = pq.dequeue();
            sb.push(next[0]);

            if (next[1] > 1) {
                next[1]--;
                pq.enqueue(next);
            }
            pq.enqueue(cur);
        } else {
            sb.push(cur[0]);
            if (cur[1] > 1) {
                cur[1]--;
                pq.enqueue(cur);
            }
        }
    }

    return String.fromCharCode(...sb);
}

type pair struct {
	c   byte
	num int
}

type hp []pair

func (a hp) Len() int           { return len(a) }
func (a hp) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool { return a[i].num > a[j].num }
func (a *hp) Push(x any)        { *a = append(*a, x.(pair)) }
func (a *hp) Pop() any          { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func longestDiverseString(a int, b int, c int) string {
	var h hp
	if a > 0 {
		heap.Push(&h, pair{'a', a})
	}
	if b > 0 {
		heap.Push(&h, pair{'b', b})
	}
	if c > 0 {
		heap.Push(&h, pair{'c', c})
	}

	var ans []byte
	for len(h) > 0 {
		cur := heap.Pop(&h).(pair)
		if len(ans) >= 2 && ans[len(ans)-1] == cur.c && ans[len(ans)-2] == cur.c {
			if len(h) == 0 {
				break
			}
			next := heap.Pop(&h).(pair)
			ans = append(ans, next.c)
			if next.num > 1 {
				next.num--
				heap.Push(&h, next)
			}
			heap.Push(&h, cur)
		} else {
			ans = append(ans, cur.c)
			if cur.num > 1 {
				cur.num--
				heap.Push(&h, cur)
			}
		}
	}

	return string(ans)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Priority Queue	Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3). Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts).
Simulated Annealing Strategy	Time Complexity: O(k! * n) with 3! possible entry sequences to maximize successful length under constraints. Space Complexity: O(1), minimal additional structures beyond temporary allocations.
Greedy + Priority Queue	–

Approach

Complexity

Greedy Approach with Priority Queue

Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3).

Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts).

Simulated Annealing Strategy

Time Complexity: O(k! * n) with 3! possible entry sequences to maximize successful length under constraints.

Space Complexity: O(1), minimal additional structures beyond temporary allocations.

Greedy + Priority Queue

–

Complexity analysis

Approach	Time	Space	When to Use
Greedy with Priority Queue	O(n log 3) ≈ O(n)	O(1)	Best general solution. Efficiently builds the longest valid string while preventing three consecutive characters.
Simulated Annealing Strategy	~O(n * k)	O(n)	Useful for experimentation with probabilistic optimization, not typically used in interviews.

Frequently asked questions

Is Longest Happy String easy or hard?

Longest Happy String is rated Medium difficulty. The challenge comes from enforcing the "no three consecutive characters" constraint while maximizing length. Once the greedy heap idea is recognized, the implementation becomes straightforward.

How to solve Longest Happy String in O(n)?

Build the result greedily while tracking remaining counts of 'a', 'b', and 'c'. Use a max heap to repeatedly choose the character with the largest count, but skip it if the last two characters in the string are the same. If that happens, use the second-largest count instead. Because the heap size is only three, the algorithm behaves like O(n) time.

Longest Happy String Python or Java solution?

Both Python and Java implementations use the same greedy heap strategy. Python typically uses the heapq module with negative counts to simulate a max heap, while Java uses PriorityQueue with a custom comparator. The logic remains identical: repeatedly append the highest-count character unless it would form three consecutive letters.

What is the best approach for Longest Happy String?

The greedy approach using a priority queue is the best solution. It always selects the character with the highest remaining count while ensuring the last two characters in the result do not create a triple. The heap guarantees efficient selection of the next candidate. This approach runs in O(n log 3) time, effectively O(n), with constant auxiliary space.

What data structure is used in Longest Happy String?

The typical implementation uses a max heap (priority queue) to track the remaining counts of each character. The heap allows efficient retrieval of the character with the largest frequency while dynamically updating counts after each append operation.

What is the time complexity of Longest Happy String?

The optimal greedy heap solution runs in O(n log 3) time, where n is the total number of characters (a + b + c). Since the heap contains at most three elements, log 3 is constant, making the overall runtime effectively O(n). Space complexity is O(1) excluding the output string.

Is Longest Happy String asked at Google, Amazon, or Meta?

Variants of this greedy string construction problem appear in interviews at companies like Google and Amazon. Interviewers use it to evaluate understanding of greedy strategies, priority queues, and constraint-based string building.

Longest Happy String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Priority Queue

Approach 2: Simulated Annealing Strategy

Approach 3: Greedy + Priority Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Happy String solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Priority Queue

Approach 2: Simulated Annealing Strategy

Approach 3: Greedy + Priority Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems