Problem Description

You are given three integers: a, b, and c, representing the maximum number of letters 'a', 'b', and 'c' you can use, respectively.
Your task is to construct the longest possible "happy" string using at most a 'a's, b 'b's, and c 'c's, subject to these constraints:

• A "happy" string is any string that does not contain three identical consecutive letters (i.e., no "aaa", "bbb", or "ccc" as a substring).
• You may use each letter up to its given maximum count.
• Return any string that is as long as possible and satisfies the above conditions.

Thought Process

At first glance, we might consider brute-forcing all possible permutations of 'a', 'b', and 'c', checking if each is "happy". However, this approach is computationally infeasible due to the sheer number of possible strings as the counts grow.

Instead, we should focus on a greedy strategy. The key insight is that to maximize the string length, we should always try to use the letter with the highest remaining count, unless doing so would create three consecutive identical letters. If it would, we pick the next most frequent letter instead.

This is similar to always picking the most "plentiful" resource unless a rule prevents us, in which case we pick the next best option. We repeat this process until no valid moves remain.

Solution Approach

The solution can be broken down into the following steps:

1. Track the counts: Store the remaining count for each letter ('a', 'b', 'c'). This can be done using a list or max-heap for efficient selection.
2. Greedy selection: At each step, select the letter with the highest remaining count that doesn't cause three consecutive identical letters in the result string.
3. Placement rules: If the last two letters in the current string are the same as the letter you want to add, skip to the next most available letter. If no valid letter can be added, stop.
4. Repeat: Continue this process, updating counts as letters are used, until no more valid letters can be added.

Example Walkthrough

Let's walk through an example with a = 1, b = 1, c = 7.

1. Initial counts: [('c', 7), ('b', 1), ('a', 1)]
2. Pick 'c' (most abundant): result = "c", counts: c=6, b=1, a=1
3. Again pick 'c': result = "cc", counts: c=5, b=1, a=1
4. Can't pick 'c' again (would make "ccc"). Pick next highest, 'b': result = "ccb", counts: c=5, b=0, a=1
5. Pick 'c': result = "ccbc", counts: c=4, b=0, a=1
6. Pick 'c': result = "ccbcc", counts: c=3, b=0, a=1
7. Can't pick 'c' again (would make "ccc"). Pick 'a': result = "ccbcca", counts: c=3, b=0, a=0
8. Pick 'c': result = "ccbccac", counts: c=2, b=0, a=0
9. Pick 'c': result = "ccbccacc", counts: c=1, b=0, a=0
10. Can't pick 'c' again (would make "ccc"). No other letters available. Stop.

Time and Space Complexity

Brute-force approach:

• Time: Exponential in a + b + c (since all possible orderings are considered).
• Space: Also exponential, due to storing all candidate strings.

• Time: O(a + b + c), since at each step we add one letter (total steps ≤ a + b + c), and selection is O(1) or O(log 3) (heap of size 3).
• Space: O(a + b + c) for the result string.

Summary

To solve the "Longest Happy String" problem, we use a greedy strategy: always append the most available letter unless it would create three in a row, in which case we pick the next best option. This efficiently builds the longest valid string by avoiding forbidden substrings and making the best local choice at each step. The approach is simple, elegant, and runs in linear time relative to the total number of letters allowed.

Code Implementation

import heapq

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        max_heap = []
        for cnt, ch in [(-a, 'a'), (-b, 'b'), (-c, 'c')]:
            if cnt != 0:
                heapq.heappush(max_heap, (cnt, ch))
        
        result = []
        while max_heap:
            cnt1, ch1 = heapq.heappop(max_heap)
            if len(result) >= 2 and result[-1] == result[-2] == ch1:
                if not max_heap:
                    break
                cnt2, ch2 = heapq.heappop(max_heap)
                result.append(ch2)
                cnt2 += 1
                if cnt2 != 0:
                    heapq.heappush(max_heap, (cnt2, ch2))
                heapq.heappush(max_heap, (cnt1, ch1))
            else:
                result.append(ch1)
                cnt1 += 1
                if cnt1 != 0:
                    heapq.heappush(max_heap, (cnt1, ch1))
        return ''.join(result)
      

#include <queue>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int, char>> pq;
        if (a) pq.push({a, 'a'});
        if (b) pq.push({b, 'b'});
        if (c) pq.push({c, 'c'});
        string res = "";
        while (!pq.empty()) {
            auto [cnt1, ch1] = pq.top(); pq.pop();
            int len = res.size();
            if (len >= 2 && res[len-1] == ch1 && res[len-2] == ch1) {
                if (pq.empty()) break;
                auto [cnt2, ch2] = pq.top(); pq.pop();
                res += ch2;
                if (--cnt2) pq.push({cnt2, ch2});
                pq.push({cnt1, ch1});
            } else {
                res += ch1;
                if (--cnt1) pq.push({cnt1, ch1});
            }
        }
        return res;
    }
};
      

import java.util.*;

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, 'a'});
        if (b > 0) pq.offer(new int[]{b, 'b'});
        if (c > 0) pq.offer(new int[]{c, 'c'});
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            int len = sb.length();
            if (len >= 2 && sb.charAt(len-1) == first[1] && sb.charAt(len-2) == first[1]) {
                if (pq.isEmpty()) break;
                int[] second = pq.poll();
                sb.append((char)second[1]);
                if (--second[0] > 0) pq.offer(second);
                pq.offer(first);
            } else {
                sb.append((char)first[1]);
                if (--first[0] > 0) pq.offer(first);
            }
        }
        return sb.toString();
    }
}
      

var longestDiverseString = function(a, b, c) {
    let arr = [];
    if (a > 0) arr.push([a, 'a']);
    if (b > 0) arr.push([b, 'b']);
    if (c > 0) arr.push([c, 'c']);
    let res = [];
    while (arr.length > 0) {
        arr.sort((x, y) => y[0] - x[0]);
        let [cnt1, ch1] = arr[0];
        let len = res.length;
        if (len >= 2 && res[len-1] === ch1 && res[len-2] === ch1) {
            if (arr.length < 2) break;
            let [cnt2, ch2] = arr[1];
            res.push(ch2);
            if (--cnt2 === 0) arr.splice(1, 1);
            else arr[1][0] = cnt2;
        } else {
            res.push(ch1);
            if (--cnt1 === 0) arr.shift();
            else arr[0][0] = cnt1;
        }
    }
    return res.join('');
};