Longest Happy String

LeetCode 1304 | Difficulty: Medium

Medium

Problem Description

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  0`

Topics: String, Greedy, Heap (Priority Queue)

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 107 ms)

Metric	Value
Runtime	107 ms
Memory	35.3 MB
Date	2022-02-02

Solution

public class Solution {
    public string LongestDiverseString(int a, int b, int c) {
        int count1 = 0, count2= 0, count3 = 0;
    int size = a+b+c;
    int i=0;
    StringBuilder sb = new StringBuilder();
    while(i++<size)
    {
        if(((a>=b && a>=c) || (count2==2 || count3==2)) && (count1<2 && a>0))
        {
            sb.Append("a");
            count1++;
            count2 = 0; count3=0;a--;
        }
        else if (((b >= a && b >= c) || (count1 == 2 || count3 == 2)) && (count2 < 2 && b > 0))
        {
            sb.Append("b");
            count2++;
            count1 = 0; count3 = 0; b--;
        }
        else if (((c >= a && c >= b) || (count1 == 2 || count2 == 2)) && (count3 < 2 && c > 0))
        {
            sb.Append("c");
            count3++;
            count1 = 0; count2 = 0; c--;
        }
        else return sb.ToString();
    }
    return sb.ToString();
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use a greedy approach.

Hint 2: Use the letter with the maximum current limit that can be added without breaking the condition.