Skip to main content
CodePeetCodePeet
CodePeet 250

Longest Happy String

MEDIUMProblemSolveExternal Links

Description

A string is called happy if it meets all of the following conditions:

  1. It contains only the characters 'a', 'b', and 'c'.
  2. It does not contain "aaa", "bbb", or "ccc" as a substring — in other words, no character may appear three times consecutively.
  3. It uses at most a copies of 'a', at most b copies of 'b', and at most c copies of 'c'.

Given three integers a, b, and c, construct and return the longest possible happy string. If multiple answers share the maximum length, return any one of them. If no happy string can be formed at all, return the empty string "".

Examples

Example 1

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

Output: "ccaccbcc"

Explanation: We have 1 'a', 1 'b', and 7 'c's available. The output uses all 1 'a', 1 'b', and 6 of the 7 'c's. No character appears three times in a row. Another valid answer is "ccbccacc". We cannot use all 7 'c's because at least two other characters are needed to break up the consecutive runs of 'c'.

Example 2

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

Output: "aabaa"

Explanation: We have 7 'a's, 1 'b', and 0 'c's. The best we can do is "aabaa", which uses 4 of the 7 'a's and the single 'b'. We place 'b' in the middle to break what would otherwise be a run of three or more 'a's. The remaining 3 'a's cannot be used without violating the constraint.

Example 3

Input: a = 0, b = 0, c = 3

Output: "cc"

Explanation: We only have 'c' characters available. We can place at most two in a row, so the longest happy string is "cc" of length 2.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to approach this problem is to try building every possible string character by character. At each position we have up to three choices — append 'a', 'b', or 'c' — as long as doing so does not create three identical characters in a row and we have not exceeded the allowed count for that character.

Imagine you are stacking coloured blocks from three bins (one bin per colour). You pick a block, place it on the line, then choose the next one. If placing a particular colour would make three of the same colour in a row at the top, you skip that colour and try another. You keep going until no colour can be placed without breaking the rule.

We can implement this with recursion (or backtracking): at each recursive call we try every valid character, recurse deeper, and track the longest result we have seen so far.

Step-by-Step Explanation

Let us trace a small example: a = 1, b = 1, c = 2.

Step 1: Start with an empty string "". Remaining counts: a=1, b=1, c=2. We can try appending 'a', 'b', or 'c'.

Step 2: Try appending 'c' first (the most plentiful character). String becomes "c", remaining c=1.

Step 3: From "c", try appending 'c' again. String becomes "cc", remaining c=0. The last two characters are both 'c', so the next character cannot be 'c'.

Step 4: From "cc", try 'a'. String becomes "cca", remaining a=0.

Step 5: From "cca", try 'b'. String becomes "ccab", remaining b=0. All counts are zero — we used every character. Length = 4.

Step 6: Backtrack and explore other branches. For instance from "cc" try 'b' instead to get "ccb", then 'a' to get "ccba". This also has length 4.

Step 7: We continue exploring all branches, keeping track of the longest valid string found. Many branches lead to shorter strings or dead ends.

Step 8: After exhausting all possibilities, we return "ccab" (or any equally long answer). The brute force guarantees correctness by checking every possibility, but it is extremely slow for large inputs.

Algorithm

  1. Define a recursive function that receives the current string and remaining counts of a, b, c.
  2. At each call, try appending each of 'a', 'b', 'c' if:
    • The remaining count for that character is greater than zero.
    • Appending it would not create three consecutive identical characters.
  3. For each valid choice, recurse with the updated string and decremented count.
  4. If no character can be appended, the current string is a candidate — compare its length with the best found so far.
  5. Return the longest string discovered across all recursive paths.

Code

class Solution {
public:
    string best;

    void solve(string& cur, int a, int b, int c) {
        if (cur.size() > best.size()) {
            best = cur;
        }
        for (auto [ch, cnt] : vector<pair<char,int>>{{'a',a},{'b',b},{'c',c}}) {
            if (cnt <= 0) continue;
            int n = cur.size();
            if (n >= 2 && cur[n-1] == ch && cur[n-2] == ch) continue;
            cur.push_back(ch);
            int na = a - (ch == 'a');
            int nb = b - (ch == 'b');
            int nc = c - (ch == 'c');
            solve(cur, na, nb, nc);
            cur.pop_back();
        }
    }

    string longestDiverseString(int a, int b, int c) {
        best = "";
        string cur = "";
        solve(cur, a, b, c);
        return best;
    }
};
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        best = [""]

        def solve(cur: list, ra: int, rb: int, rc: int):
            candidate = "".join(cur)
            if len(candidate) > len(best[0]):
                best[0] = candidate

            for ch, cnt in [('a', ra), ('b', rb), ('c', rc)]:
                if cnt <= 0:
                    continue
                n = len(cur)
                if n >= 2 and cur[-1] == ch and cur[-2] == ch:
                    continue
                cur.append(ch)
                na = ra - (1 if ch == 'a' else 0)
                nb = rb - (1 if ch == 'b' else 0)
                nc = rc - (1 if ch == 'c' else 0)
                solve(cur, na, nb, nc)
                cur.pop()

        solve([], a, b, c)
        return best[0]
class Solution {
    String best = "";

    public String longestDiverseString(int a, int b, int c) {
        best = "";
        solve(new StringBuilder(), a, b, c);
        return best;
    }

    private void solve(StringBuilder cur, int a, int b, int c) {
        if (cur.length() > best.length()) {
            best = cur.toString();
        }
        char[] chars = {'a', 'b', 'c'};
        int[] counts = {a, b, c};
        for (int i = 0; i < 3; i++) {
            if (counts[i] <= 0) continue;
            int n = cur.length();
            if (n >= 2 && cur.charAt(n - 1) == chars[i]
                       && cur.charAt(n - 2) == chars[i]) continue;
            cur.append(chars[i]);
            int na = a - (chars[i] == 'a' ? 1 : 0);
            int nb = b - (chars[i] == 'b' ? 1 : 0);
            int nc = c - (chars[i] == 'c' ? 1 : 0);
            solve(cur, na, nb, nc);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

Complexity Analysis

Time Complexity: O(3^(a+b+c))

At each of the up to a + b + c positions we may branch into up to 3 choices. This creates an exponential recursion tree. For a + b + c = 300 (the maximum), 3^300 is astronomically large and completely impractical.

Space Complexity: O(a + b + c)

The recursion depth can reach a + b + c, and we store the current string of that length on the call stack.

Why This Approach Is Not Efficient

The brute force explores an exponential number of branches — up to 3^(a+b+c). With the constraint a + b + c ≤ 300, that could mean up to 3^300 possibilities, a number far beyond what any computer could enumerate.

The core waste is that we explore many paths that differ only in the order of characters placed at positions that do not affect the final length. For example, placing 'a' then 'b' at positions 5-6 versus 'b' then 'a' might lead to equally long results, yet we explore both.

The key insight is that we do not need to try all possibilities. At each position, there is a locally optimal choice — always using the character with the highest remaining count (as long as it does not violate the three-in-a-row rule). This greedy observation eliminates the need for backtracking entirely.

Better Approach - Greedy with Sorting

Intuition

Instead of exploring every possible string, we can build the answer greedily — one character at a time — by always picking the character that has the most remaining uses, as long as it does not create three in a row.

Why does picking the most frequent character work? Imagine you have 10 red balls, 2 blue balls, and 1 green ball, and you need to line them up so no three consecutive balls share the same colour. If you use up the blue and green balls early, you will be stuck with many red balls that you cannot place. By always prioritising the colour with the highest count, you spread the dominant colour across the string and interleave the less frequent ones as spacers when needed.

To find the character with the highest count at each step, we can sort the three (character, count) pairs in descending order. We pick the first one that is safe; if it would cause three in a row, we pick the second one. After placing a character, we decrement its count and sort again for the next position.

Step-by-Step Explanation

Let us trace with a = 1, b = 1, c = 4.

Step 1: Counts: {c:4, a:1, b:1}. Sort descending. Result: "".

Step 2: Top is 'c' (count 4). Result is empty — safe. Append 'c'. Decrement c to 3. Result: "c".

Step 3: Re-sort. Top is 'c' (count 3). Last char is 'c' but only one — safe. Append 'c'. c drops to 2. Result: "cc".

Step 4: Re-sort. Top is 'c' (count 2). Last two chars are "cc" — appending 'c' would make "ccc". BLOCKED. Skip to second-highest: 'a' (count 1). 'a' is safe. Append 'a'. a drops to 0. Result: "cca".

Step 5: Re-sort. Top is 'c' (count 2). Last two are "ca" — safe. Append 'c'. c drops to 1. Result: "ccac".

Step 6: Re-sort. Top is 'c' (count 1). Last two are "ac" — safe. Append 'c'. c drops to 0. Result: "ccacc".

Step 7: Re-sort. Top is 'b' (count 1). Last two are "cc" but 'b' is different — safe. Append 'b'. b drops to 0. Result: "ccaccb".

Step 8: All counts zero. Stop. Final answer: "ccaccb" (length 6, all characters used).

Greedy with Sorting — Building the Longest Happy String — Watch how we sort character counts at each step, pick the most frequent safe character, and grow the result string one letter at a time.

Algorithm

  1. Create a list of (character, count) pairs for all characters with count > 0.
  2. Repeat until no character can be placed:
    a. Sort the list in descending order of count.
    b. Pick the character with the highest count. If the last two characters of the result are the same as this character, skip it and pick the next highest.
    c. Append the chosen character to the result string.
    d. Decrement that character's count. If it reaches zero, remove it from the list.
  3. Return the result string.

Code

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string result;
        vector<pair<int,char>> counts = {{a,'a'},{b,'b'},{c,'c'}};

        while (true) {
            sort(counts.begin(), counts.end(), greater<>());
            bool placed = false;
            for (auto& [cnt, ch] : counts) {
                if (cnt == 0) continue;
                int n = result.size();
                if (n >= 2 && result[n-1] == ch && result[n-2] == ch) {
                    continue;
                }
                result.push_back(ch);
                cnt--;
                placed = true;
                break;
            }
            if (!placed) break;
        }
        return result;
    }
};
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        counts = [['a', a], ['b', b], ['c', c]]
        result = []

        while True:
            counts.sort(key=lambda x: -x[1])
            placed = False
            for pair in counts:
                ch, cnt = pair
                if cnt == 0:
                    continue
                n = len(result)
                if n >= 2 and result[-1] == ch and result[-2] == ch:
                    continue
                result.append(ch)
                pair[1] -= 1
                placed = True
                break
            if not placed:
                break

        return "".join(result)
class Solution {
    public String longestDiverseString(int a, int b, int c) {
        int[][] counts = {{a, 0}, {b, 1}, {c, 2}};
        char[] chars = {'a', 'b', 'c'};
        StringBuilder result = new StringBuilder();

        while (true) {
            Arrays.sort(counts, (x, y) -> y[0] - x[0]);
            boolean placed = false;
            for (int[] pair : counts) {
                if (pair[0] == 0) continue;
                int n = result.length();
                char ch = chars[pair[1]];
                if (n >= 2 && result.charAt(n - 1) == ch
                           && result.charAt(n - 2) == ch) {
                    continue;
                }
                result.append(ch);
                pair[0]--;
                placed = true;
                break;
            }
            if (!placed) break;
        }
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n · k log k) where n = a + b + c and k = 3

We iterate at most n times (once per character placed). At each iteration we sort k = 3 elements, costing O(k log k). Since k = 3 is constant, this simplifies to O(n) in practice. However, conceptually the repeated sorting is unnecessary overhead compared to a heap-based approach.

Space Complexity: O(n)

The result string can have up to n characters. The counts list uses O(k) = O(1) extra space.

Why This Approach Is Not Efficient

Although the greedy-with-sorting approach effectively runs in O(n) time (since k = 3 is constant), it conceptually performs redundant work by sorting all three counts from scratch at every step. This matters more when generalised to k distinct characters — the sort would cost O(k log k) per step, making the total O(n · k log k).

A max-heap (priority queue) maintains the sorted order incrementally: extracting the maximum costs O(log k), and reinserting an updated count also costs O(log k). We never need to re-sort the whole list. For k = 3 the practical difference is negligible, but the heap-based approach is the canonical, scalable solution and is also slightly cleaner because it naturally handles zero-count characters by simply not reinserting them.

Optimal Approach - Greedy with Max Heap

Intuition

The greedy logic is identical to the sorting approach — always pick the character with the most remaining uses — but instead of sorting an array every time, we maintain a max-heap (priority queue) that keeps the characters ordered by their remaining count.

The algorithm works in a loop:

  1. Pop the top of the heap — this is the character with the highest remaining count.
  2. Check whether using this character would create three identical characters in a row (by looking at the last two characters of the result).
    • If it would cause a violation: pop the second element from the heap, use that character instead, and push the first one back unchanged.
    • If no second element exists, we are stuck and must stop.
  3. If it is safe: append it to the result, decrement its count, and push it back into the heap only if its count is still positive.
  4. Repeat until the heap is empty or no valid placement exists.

Since the heap has at most 3 elements, every push and pop is O(log 3) = O(1). The total work is proportional to the length of the result string, which is at most a + b + c.

Step-by-Step Explanation

Let us trace with a = 1, b = 1, c = 4.

Step 1: Build the max-heap from nonzero counts: heap = [(c,4), (a,1), (b,1)]. Result = "".

Step 2: Pop top → (c, 4). Result is empty, no triple risk. Append 'c'. Decrement c to 3, push back. Heap: [(c,3), (a,1), (b,1)]. Result: "c".

Step 3: Pop top → (c, 3). Last char is 'c' but only one consecutive — safe. Append 'c'. c becomes 2, push back. Heap: [(c,2), (a,1), (b,1)]. Result: "cc".

Step 4: Pop top → (c, 2). Last two chars are "cc" — BLOCKED! Pop next → (a, 1). 'a' differs from 'c', safe. Append 'a'. a becomes 0, do not push back. Push (c,2) back unchanged. Heap: [(c,2), (b,1)]. Result: "cca".

Step 5: Pop top → (c, 2). Last two are "ca" — safe. Append 'c'. c becomes 1, push back. Heap: [(c,1), (b,1)]. Result: "ccac".

Step 6: Pop top → (c, 1). Last two are "ac" — safe. Append 'c'. c becomes 0, do not push back. Heap: [(b,1)]. Result: "ccacc".

Step 7: Pop top → (b, 1). Last two are "cc" but 'b' differs from 'c' — safe. Append 'b'. b becomes 0, do not push back. Heap: []. Result: "ccaccb".

Step 8: Heap is empty. Stop. Return "ccaccb" (length 6).

Greedy Max-Heap — Always Pick the Most Frequent Safe Character — Watch the max-heap maintain character priorities as we greedily build the longest happy string, switching to the second-highest when the top character would cause three in a row.

Algorithm

  1. Push every character with a positive count into a max-heap as (count, character).
  2. While the heap is not empty:
    a. Pop the top element (highest count).
    b. If the last two characters of the result equal this character:
    • If the heap is empty, stop (no valid character available).
    • Pop the next element, append its character to the result, decrement its count, push it back if count > 0.
    • Push the original top element back unchanged.
      c. Otherwise, append the top character to the result, decrement its count, push back if count > 0.
  3. Return the result string.

Code

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int,char>> pq;
        if (a > 0) pq.push({a, 'a'});
        if (b > 0) pq.push({b, 'b'});
        if (c > 0) pq.push({c, 'c'});

        string result;

        while (!pq.empty()) {
            auto [cnt1, ch1] = pq.top(); pq.pop();
            int n = result.size();

            if (n >= 2 && result[n-1] == ch1 && result[n-2] == ch1) {
                if (pq.empty()) break;
                auto [cnt2, ch2] = pq.top(); pq.pop();
                result.push_back(ch2);
                if (cnt2 - 1 > 0) pq.push({cnt2 - 1, ch2});
                pq.push({cnt1, ch1});
            } else {
                result.push_back(ch1);
                if (cnt1 - 1 > 0) pq.push({cnt1 - 1, ch1});
            }
        }

        return result;
    }
};
import heapq

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        heap = []
        if a > 0:
            heapq.heappush(heap, (-a, 'a'))
        if b > 0:
            heapq.heappush(heap, (-b, 'b'))
        if c > 0:
            heapq.heappush(heap, (-c, 'c'))

        result = []

        while heap:
            neg_cnt1, ch1 = heapq.heappop(heap)
            if len(result) >= 2 and result[-1] == ch1 and result[-2] == ch1:
                if not heap:
                    break
                neg_cnt2, ch2 = heapq.heappop(heap)
                result.append(ch2)
                if neg_cnt2 + 1 < 0:
                    heapq.heappush(heap, (neg_cnt2 + 1, ch2))
                heapq.heappush(heap, (neg_cnt1, ch1))
            else:
                result.append(ch1)
                if neg_cnt1 + 1 < 0:
                    heapq.heappush(heap, (neg_cnt1 + 1, ch1))

        return "".join(result)
class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        if (a > 0) pq.offer(new int[]{a, 0});
        if (b > 0) pq.offer(new int[]{b, 1});
        if (c > 0) pq.offer(new int[]{c, 2});

        char[] chars = {'a', 'b', 'c'};
        StringBuilder result = new StringBuilder();

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int cnt1 = top[0];
            char ch1 = chars[top[1]];
            int n = result.length();

            if (n >= 2 && result.charAt(n - 1) == ch1
                       && result.charAt(n - 2) == ch1) {
                if (pq.isEmpty()) break;
                int[] second = pq.poll();
                int cnt2 = second[0];
                char ch2 = chars[second[1]];
                result.append(ch2);
                if (cnt2 - 1 > 0) pq.offer(new int[]{cnt2 - 1, second[1]});
                pq.offer(top);
            } else {
                result.append(ch1);
                if (cnt1 - 1 > 0) pq.offer(new int[]{cnt1 - 1, top[1]});
            }
        }

        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(a + b + c)

The main loop runs at most a + b + c times because each iteration appends exactly one character to the result. Each heap operation (push or pop) on a heap of at most 3 elements takes O(log 3) = O(1) time. Therefore the total work is O(a + b + c).

Space Complexity: O(a + b + c)

The result string has at most a + b + c characters, which dominates the space usage. The heap itself uses O(3) = O(1) extra space.