LeetCode 1405 - Longest Happy String

LeetCode Problem 1405

Difficulty: 🟡 Medium
Topics: String, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to construct the longest possible string using only the characters 'a', 'b', and 'c', while satisfying a very important restriction: the string cannot contain three consecutive identical characters. In other words, substrings like "aaa", "bbb", and "ccc" are forbidden.

We are given three integers:

• a, the maximum number of 'a' characters we may use
• b, the maximum number of 'b' characters we may use
• c, the maximum number of 'c' characters we may use

The goal is to build the longest valid string possible. We do not need to use every character. Sometimes it is impossible to use all available letters because doing so would force three identical characters in a row.

For example, if we have many more 'c' characters than the others, we cannot simply append all of them consecutively. We must strategically insert other letters between them to avoid violating the happy string condition.

The constraints are relatively small:

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

Since the total number of characters is at most 300, even moderately expensive algorithms could work. However, the structure of the problem strongly suggests a greedy strategy because at every step we want to choose the character that helps maximize the final string length without creating an invalid sequence.

Several edge cases are important:

• One or two character counts may be zero.
• One character count may dominate the others heavily, such as (7,1,0).
• All counts may already be balanced.
• A naive greedy strategy may accidentally create a dead end where no valid character can be appended, even though another earlier choice would have allowed a longer result.

The problem guarantees that at least one character is available because a + b + c > 0.

Approaches

Brute Force Approach

A brute force solution would try every possible valid string recursively. At each position, we could attempt to append 'a', 'b', or 'c' if:

1. We still have remaining count for that character.
2. Appending it would not create three consecutive identical letters.

We would recursively explore every valid continuation and keep track of the longest result found.

This approach is correct because it examines every possible valid happy string and therefore cannot miss the optimal answer.

However, it is extremely inefficient. The number of possible strings grows exponentially with the total number of characters. Even with pruning, the recursive search space becomes very large as counts increase toward 100.

Optimal Greedy Approach

The key observation is that we should always try to use the character with the largest remaining count, because leaving too many copies of a single character unused later may make them impossible to place.

However, we cannot blindly append the most frequent character every time. If the last two characters in the current result are already the same as that character, adding another would violate the happy string rule.

This naturally leads to a greedy strategy with a max heap:

• Store available characters ordered by remaining frequency.
• Repeatedly choose the character with the highest remaining count.
• If it would create three consecutive identical characters, temporarily use the second most frequent character instead.
• After using a character, decrease its count and push it back into the heap if copies remain.

This strategy always prioritizes the most abundant character while safely avoiding invalid triples.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^(a+b+c))	O(a+b+c)	Explores every valid string recursively
Optimal	O((a+b+c) log 3)	O(1)	Greedy heap-based construction

Because there are only three characters, log 3 is effectively constant, making the solution extremely efficient in practice.

Algorithm Walkthrough

Optimal Greedy Heap Algorithm

1. Create a max heap containing all characters with positive remaining counts.

Each heap entry stores:

• negative count, because Python's heapq is a min heap
• the character itself

For example:

[(-7, 'c'), (-1, 'a'), (-1, 'b')]

2. Initialize an empty result list.

We use a list instead of repeated string concatenation because appending to a list is more efficient. 3. Repeatedly extract the character with the largest remaining count.

This greedy choice attempts to use the most abundant character first so that we do not get stuck with many unusable copies later. 4. Before appending the character, check whether it would create three consecutive identical letters.

Specifically:

• if the last two characters in the result are both equal to the candidate character
• then appending it would violate the happy string condition

5. If the character cannot be used safely:

• remove the second most frequent character from the heap
• append that character instead
• decrease its count
• push it back if copies remain
• finally push the original blocked character back into the heap

6. If no alternative character exists, stop.

This means no valid extension of the string is possible. 7. If the character is safe to append:

• append it to the result
• decrease its remaining count
• push it back if copies remain

8. Continue until the heap becomes empty or no valid move exists.
9. Join the result list into a final string and return it.

Why it works

The algorithm maintains an important invariant: the current string is always valid and never contains three consecutive identical characters.

At every step, we greedily use the character with the highest remaining count whenever possible. This minimizes the risk of leaving too many copies of one character unused later. If the best character cannot be used safely, the algorithm temporarily uses the next best alternative to preserve validity.

Because every step either safely uses the most abundant character or the best available fallback, the algorithm constructs a longest possible happy string.

Python Solution

from heapq import heappush, heappop
from typing import List

class Solution:
    def longestDiverseString(self, 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)

            # Check whether adding this character
            # would create three consecutive letters
            if (
                len(result) >= 2 and
                result[-1] == char1 and
                result[-2] == char1
            ):
                # No alternative character exists
                if not max_heap:
                    break

                count2, char2 = heappop(max_heap)

                result.append(char2)
                count2 += 1

                if count2 < 0:
                    heappush(max_heap, (count2, char2))

                heappush(max_heap, (count1, char1))

            else:
                result.append(char1)
                count1 += 1

                if count1 < 0:
                    heappush(max_heap, (count1, char1))

        return ''.join(result)

The implementation begins by building a max heap containing all characters with positive counts. Since Python's heapq implements a min heap, negative counts are used so that larger frequencies appear first.

The result list stores the characters of the final string incrementally. A list is preferred over repeated string concatenation because appending to a list is more efficient.

Inside the main loop, the algorithm removes the character with the highest remaining frequency. Before appending it, the code checks whether the last two characters in the current result already match this character. If they do, appending it would create an invalid substring such as "aaa".

When that happens, the algorithm temporarily chooses the second most frequent character instead. After using the alternative character, the blocked character is pushed back into the heap so it can be reconsidered later.

If no alternative exists, construction stops because no valid extension is possible.

The counts are updated after every append operation. Since counts are stored as negatives, incrementing the value moves it toward zero.

Finally, the result list is joined into a string and returned.

Go Solution

package main

import (
	"container/heap"
)

type Node struct {
	count int
	char  byte
}

type MaxHeap []Node

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i].count > h[j].count
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func longestDiverseString(a int, b int, c int) string {
	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	if a > 0 {
		heap.Push(maxHeap, Node{count: a, char: 'a'})
	}

	if b > 0 {
		heap.Push(maxHeap, Node{count: b, char: 'b'})
	}

	if c > 0 {
		heap.Push(maxHeap, Node{count: c, char: 'c'})
	}

	result := make([]byte, 0)

	for maxHeap.Len() > 0 {
		first := heap.Pop(maxHeap).(Node)

		n := len(result)

		if n >= 2 &&
			result[n-1] == first.char &&
			result[n-2] == first.char {

			if maxHeap.Len() == 0 {
				break
			}

			second := heap.Pop(maxHeap).(Node)

			result = append(result, second.char)
			second.count--

			if second.count > 0 {
				heap.Push(maxHeap, second)
			}

			heap.Push(maxHeap, first)

		} else {
			result = append(result, first.char)
			first.count--

			if first.count > 0 {
				heap.Push(maxHeap, first)
			}
		}
	}

	return string(result)
}

The Go implementation follows the same greedy heap strategy as the Python version. Since Go does not provide a built in max heap, we implement the heap.Interface manually and reverse the comparison in the Less method so that larger counts have higher priority.

Instead of storing characters in a string builder directly, the implementation uses a []byte slice for efficient append operations. At the end, the byte slice is converted into a string.

Unlike Python's negative-count trick, the Go implementation stores counts as positive integers because the custom heap ordering already behaves like a max heap.

Worked Examples

Example 1

Input: a = 1, b = 1, c = 7

Initial heap:

[(7,c), (1,a), (1,b)]

Step	Result	Heap Top Choice	Action
1	c	c	Safe to append
2	cc	c	Safe to append
3	cca	c	Cannot use c again, use a
4	ccac	c	Safe
5	ccacc	c	Safe
6	ccaccb	c	Cannot use c again, use b
7	ccaccbc	c	Safe
8	ccaccbcc	c	Safe

Final answer:

"ccaccbcc"

Example 2

Input: a = 7, b = 1, c = 0

Initial heap:

[(7,a), (1,b)]

Step	Result	Heap Top Choice	Action
1	a	a	Safe
2	aa	a	Safe
3	aab	a	Cannot use a again, use b
4	aaba	a	Safe
5	aabaa	a	Safe
6	stop	a	Would create aaa, no alternative

Final answer:

"aabaa"

Complexity Analysis

Measure	Complexity	Explanation
Time	O((a+b+c) log 3)	Each character insertion performs heap operations
Space	O(1)	Heap stores at most 3 characters

The heap never contains more than three entries because there are only three possible characters. Each append operation performs at most a few heap pushes and pops, each taking O(log 3) time. Since log 3 is constant, the practical runtime is effectively linear in the total number of characters.

The auxiliary space usage is constant because the heap size never grows beyond three elements. The output string itself is not counted toward auxiliary complexity.

Test Cases

def is_happy(s: str, a: int, b: int, c: int) -> bool:
    if "aaa" in s or "bbb" in s or "ccc" in s:
        return False

    return (
        s.count('a') <= a and
        s.count('b') <= b and
        s.count('c') <= c
    )

sol = Solution()

# Provided example 1
result = sol.longestDiverseString(1, 1, 7)
assert is_happy(result, 1, 1, 7)
assert len(result) == 8

# Provided example 2
result = sol.longestDiverseString(7, 1, 0)
assert result == "aabaa"

# Only one character available
result = sol.longestDiverseString(3, 0, 0)
assert result == "aa"  # cannot place third a

# Balanced counts
result = sol.longestDiverseString(2, 2, 2)
assert is_happy(result, 2, 2, 2)
assert len(result) == 6

# One dominant character
result = sol.longestDiverseString(10, 1, 1)
assert is_happy(result, 10, 1, 1)

# Smallest nonzero input
result = sol.longestDiverseString(1, 0, 0)
assert result == "a"

# Two characters only
result = sol.longestDiverseString(0, 3, 3)
assert is_happy(result, 0, 3, 3)
assert len(result) == 6

# Large balanced counts
result = sol.longestDiverseString(100, 100, 100)
assert is_happy(result, 100, 100, 100)
assert len(result) == 300

# Large imbalance
result = sol.longestDiverseString(100, 1, 1)
assert is_happy(result, 100, 1, 1)

# Another mixed configuration
result = sol.longestDiverseString(4, 4, 1)
assert is_happy(result, 4, 4, 1)
assert len(result) == 9

Test	Why
(1,1,7)	Verifies handling of heavily dominant character
(7,1,0)	Tests stopping condition when no separator exists
(3,0,0)	Ensures triple-character prevention works
(2,2,2)	Tests perfectly balanced counts
(10,1,1)	Verifies greedy selection under severe imbalance
(1,0,0)	Smallest valid input
(0,3,3)	Tests operation when one character type is missing
(100,100,100)	Stress test with maximum balanced input
(100,1,1)	Extreme imbalance stress case
(4,4,1)	Mixed distribution validation

Edge Cases

One important edge case occurs when only a single character type is available, such as (3,0,0). A naive implementation might append all three 'a' characters and produce "aaa", which is invalid. The heap-based algorithm prevents this because it explicitly checks the last two characters before every append. Once "aa" has been formed, adding another 'a' becomes forbidden, and the algorithm stops.

Another important case is when one character count is much larger than the others, such as (100,1,1). Without careful balancing, many characters would become unusable. The greedy strategy handles this correctly by repeatedly inserting separator characters whenever necessary. Eventually, the separators run out, and the algorithm terminates with the longest achievable valid string.

A third edge case happens when the most frequent character is temporarily unusable, but another valid character still exists. For example, after building "cc", another 'c' cannot be added immediately. A naive greedy solution might incorrectly stop at this point. Instead, the algorithm removes the second most frequent character from the heap and uses it as a separator, allowing construction to continue.

A final subtle case occurs when all counts are already balanced, such as (2,2,2). The algorithm still works correctly because it always prefers the currently most abundant character while maintaining validity. Since no character becomes overwhelmingly dominant, all characters can typically be used successfully.