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 <= 100a + b + c > 0The key idea in #1405 Longest Happy String is to construct the result greedily while ensuring that no character appears three times consecutively. Since we are given counts of a, b, and c, the challenge is to always pick the character with the highest remaining count without violating the constraint.
A common strategy uses a max heap (priority queue) to always access the character with the largest remaining frequency. At each step, choose the character with the highest count and append it to the result. However, before adding it, check the last two characters of the current string. If adding the same character would create three consecutive identical characters, temporarily use the next most frequent character from the heap.
After appending a character, decrease its count and push it back into the heap if it still has remaining occurrences. This greedy selection ensures we maximize the string length while maintaining the "happy" constraint. Because the number of character types is small, the heap operations remain efficient.
Time Complexity: O(n log k) where n is the resulting string length and k is the number of distinct characters. Space Complexity: O(k).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Max Heap (Priority Queue) | O(n log k) | O(k) |
| Greedy with Constant Character Set (Optimized) | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use a greedy approach.
Use the letter with the maximum current limit that can be added without breaking the condition.
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:
Once you process all characters when the heap is non-empty, the constructed string is your answer.
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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public string LongestDiverseString(int a, int b, int c) {
6 PriorityQueue<(int count, char ch)> queue = new PriorityQueue<(int, char)>(Comparer<(int, char)>.Create((x, y) => y.count.CompareTo(x.count)));
7 if (a > 0) queue.Enqueue((a, 'a'));
8 if (b > 0) queue.Enqueue((b, 'b'));
9 if (c > 0) queue.Enqueue((c, 'c'));
10
11 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 C# approach adopts a PriorityQueue for orderly character selection, considering constraints on consecutive similar characters, thus offering robust, systematic string extension without breaking the 'happy' rules.
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.
Time Complexity: O(k! * n), where k = 3 (permutations of distinct characters) and n denotes total character appearances.
Space Complexity: O(1), only a few data structures to hold options.
1#include <string>
2#include <tuple>
3
4std::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;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of greedy string construction problems like Longest Happy String appear in technical interviews at major tech companies. They test understanding of greedy strategies, priority queues, and careful constraint handling.
The optimal approach uses a greedy strategy with a max heap to always select the character with the highest remaining frequency. Before adding it, we check if the last two characters are the same to avoid three consecutive identical letters. If they are, we temporarily use the next best character.
The problem requires building the longest possible string while preventing three identical consecutive characters. Greedy selection works well because choosing the character with the highest remaining count generally maximizes the total length while maintaining the constraint.
A max heap (priority queue) works best because it lets us efficiently select the character with the highest remaining count. This ensures we always extend the string with the most available character while respecting the constraint.
The C++ code builds potential "happy" strings by iterating through all possible orders of appending triplet combinations. For each order (swapping item positions within "abc"), potential outcomes are evaluated with respect to happy constraints and count tracking. The code iteratively improves upon choices to achieve maximal string formations.