Longest Happy String - Practice Coding Problems

Longest Happy String - 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.

Input & Output

Example 1 — Basic Case

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

› Output: "ccbccac"

💡 Note: We have 7 c's, 1 a, and 1 b. Start with most frequent 'c', then alternate to avoid three consecutive c's. Result uses all characters: c-c-b-c-c-a-c.

Example 2 — Equal Counts

$ Input: a = 2, b = 2, c = 1

› Output: "aabbc"

💡 Note: With equal counts of a and b, we can use both twice. Pattern: a-a-b-b-c uses all characters optimally.

Example 3 — No Solution

$ Input: a = 0, b = 2, c = 1

› Output: "bbc"

💡 Note: Only b and c available. We can create b-b-c without violating the three consecutive rule.

Constraints

0 ≤ a, b, c ≤ 100
a + b + c > 0

Visualization

Tap to expand

Understanding the Visualization

Input

Character counts: a=1, b=1, c=7

Process

Greedily select highest count character, avoid three consecutive

Output

Happy string: "ccbccac" (length 9)

Key Takeaway

🎯 Key Insight: Always prioritize the most frequent character while strategically switching to avoid three consecutive repeats

Asked in

f Facebook 25 G Google 18 a Amazon 15

The key insight is to always use the character with the highest remaining count while ensuring no three consecutive identical characters. The optimal approach uses a priority queue (max heap) to efficiently track and select characters. Time: O((a+b+c) log 3), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O((a+b+c) * log 3)	O(1)	Always choose the character with highest count, avoiding three consecutive same characters
Priority Queue (Heap)	O((a+b+c) * log 3)	O(1)	Use max heap to efficiently track and select characters with highest counts
Brute Force Recursion	O(3^(a+b+c))	O(a+b+c)	Try all possible combinations recursively and pick the longest valid one

Greedy Approach — Algorithm Steps

Sort characters by remaining count
Pick highest count character if safe
If not safe, pick second highest
Repeat until no valid moves

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Count

Order characters by remaining count

Pick Highest

Choose character with highest count if safe

Avoid Triple

Pick second highest if last two are same

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int count;
} CharCount;

int compare(const void* a, const void* b) {
    CharCount* ca = (CharCount*)a;
    CharCount* cb = (CharCount*)b;
    return cb->count - ca->count;
}

char* solution(int a, int b, int c) {
    char* result = malloc(1000);
    int resultLen = 0;
    result[0] = '\0';
    
    CharCount counts[3] = {{'a', a}, {'b', b}, {'c', c}};
    
    while (1) {
        // Sort by count (descending)
        qsort(counts, 3, sizeof(CharCount), compare);
        
        // Check if we can use the most frequent character
        if (resultLen >= 2 && 
            result[resultLen-1] == result[resultLen-2] && 
            result[resultLen-1] == counts[0].ch) {
            // Use second most frequent to avoid three consecutive
            if (counts[1].count == 0) {
                break;
            }
            result[resultLen++] = counts[1].ch;
            result[resultLen] = '\0';
            counts[1].count--;
        } else {
            // Use most frequent character
            if (counts[0].count == 0) {
                break;
            }
            result[resultLen++] = counts[0].ch;
            result[resultLen] = '\0';
            counts[0].count--;
        }
    }
    
    return result;
}

int main() {
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    char* result = solution(a, b, c);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((a+b+c) * log 3)

Each iteration takes O(log 3) to sort 3 characters, and we do at most a+b+c iterations

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for tracking character counts

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler